﻿#include <iostream>
using namespace std;

// 1.两数之和
//
//  ways1:暴力破解
// class Solution {
// public:
//     vector<int> twoSum(vector<int>& nums, int target) {
//         for (int i = 0; i < nums.size() - 1; i++) {
//             for (int j = i + 1; j < nums.size(); j++) {宝石
//                 if (nums[i] + nums[j] == target) {
//                     return { i,j };
//					//1.return vector<int>{i, j};也可以

//              }
//            }
//        }
//        return {};//2.
//    }
//
// ways2:哈希表

// 2.   49字母异位词分组----要用哈希表

// 3.  最长连续序列

// 4.   283. 移动零
// way:双指针法。
// class Solution {
// public:
//    void moveZeroes(vector<int>& nums) {
//        int n = nums.size();   // 获取数组的大小
//        int left = 0;          // 初始化左指针，从头开始
//        int right = 0;         // 初始化右指针，从头开始
//
//        while (right < n) {    // 遍历数组，直到右指针到达数组末尾
//            if (nums[right] != 0) {  // 如果右指针指向的元素不是 0
//                swap(nums[left], nums[right]);  // 交换左右指针指向的元素
//                left++;          // 左指针右移，表示已经处理了一个非零元素
//            }
//            right++;             // 无论右指针指向的元素是不是 0，右指针都向右移动
//        }
//    }
//};

// 11.盛最多水的容器
// 我写的通过了的
// class Solution {
// public:
//    int maxArea(vector<int>& height) {
//        int sum = 0;//最大的容量。
//        int L = 0;//左指针
//        int n = height.size();//n个数据
//        int R = n - 1;//右指针
//        while (L < R)
//        {
//            if (min(height[L], height[R]) * (R - L) >= sum)
//            {
//                sum = min(height[L], height[R]) * (R - L);
//            }
//            if (height[L] >= height[R])
//            {
//                R--;
//            }
//            else
//            {
//                L++;
//            }
//        }
//        return sum;
//    }
//};

// 最大水量 = min(height[left], height[right]) * 长度，往中间移动长度一定会变短
// 如果移动高的那一边，会有两种情况：
// 1、下一根柱子的高度比现在高，高度还取最小值低的那边，最大水量比原来小
//
// 2、下一根柱子的高度比现在低，高度比原来的最小值还小，最大水量比原来小
// 如果移动低的那一边，会有两种情况：
// 1、下一根柱子的高度比现在高，高度就可以取更高的值，最大水量不一定比原来小
// 2、下一根柱子的高度比现在低，高度比原来的最小值还小，最大水量比原来小
// 所以应该移动低的那一边

// 15.三数之和
// class Solution {
// public:
//     vector<vector<int>> threeSum(vector<int>& nums) {
//         sort(nums.begin(), nums.end()); // 先排序
//         vector<vector<int>> result;
//
//         for (int i = 0; i < nums.size(); i++) {
//             // 跳过重复的nums[i]
//             if (i > 0 && nums[i] == nums[i - 1]) {
//                 continue;
//             }
//
//             int L = i + 1;
//             int R = nums.size() - 1;
//
//             // 双指针查找
//             while (L < R) {
//                 int sum = nums[i] + nums[L] + nums[R];
//
//                 if (sum == 0) {
//                     result.push_back({ nums[i], nums[L], nums[R] });
//
//                     // 避免 L 重复
//                     while (L < R && nums[L] == nums[L + 1]) {
//                         L++;
//                     }
//                     // 避免 R 重复
//                     while (L < R && nums[R] == nums[R - 1]) {
//                         R--;
//                     }
//
//                     L++; // 继续移动指针
//                     R--;
//                 }
//                 else if (sum < 0) {
//                     L++;
//                 }
//                 else {
//                     R--;
//                 }
//             }
//         }
//
//         return result;
//     }
// };

// 3. 无重复字符的最长子串————————滑动窗口、哈希表
// #include<unordered_set>
// class Solution {
// public:
//     int lengthOfLongestSubstring(string s) {
//         // 用于存储当前窗口中的字符
//         unordered_set<char> charSet;
//         // 左指针，表示窗口的起始位置
//         int left = 0;
//         // 记录最大长度
//         int maxLength = 0;
//
//         // 右指针，表示窗口的结束位置
//         for (int right = 0; right < s.length(); right++) {
//             // 如果当前字符已经在集合中，则需要缩小窗口
//             //find找不到才会返回end().
//             while (charSet.find(s[right]) != charSet.end()) {
//                 charSet.erase(s[left]);  // 从集合中移除左指针指向的字符
//                 left++;  // 缩小窗口，左指针右移
//             }
//             // 将当前字符加入集合
//             charSet.insert(s[right]);
//             // 计算并更新最大子串长度
//             maxLength = max(maxLength, right - left + 1);
//         }
//         return maxLength;  // 返回最终结果
//     }
// };

// 438. 找到字符串中所有字母异位词——————滑动窗口
// way1:
class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> result;
        if (s.size() < p.size())
            return result;

        // 用来记录字符串p的字符频率
        vector<int> pFreq(26, 0);
        // 用来记录当前窗口内的字符频率
        vector<int> windowFreq(26, 0);

        // 统计p中的字符频率
        for (char c : p)
        {
            pFreq[c - 'a']++;
        }

        int left = 0, right = 0;

        // 滑动窗口的大小为p的长度
        while (right < s.size())
        {
            // 增加窗口右边的字符
            windowFreq[s[right] - 'a']++;

            // 如果窗口大小大于p的长度，移除左边字符
            if (right - left + 1 > p.size())
            {
                windowFreq[s[left] - 'a']--;
                left++;
            }

            // 现在窗口大小已经小于等于p的长度了
            // 如果是小于，下面的if也不会通过，所以没必要再来个判断是否等于

            // 判断窗口内的字符频率是否与p相同
            // if (R - L + 1 == p.size())   :多余
            if (windowFreq == pFreq)
            {
                result.push_back(left); // 左指针是当前异位词的起始索引
            }

            // 移动右指针
            right++;
        }

        return result;
    }
};
// way2:
class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        // 获取字符串 s 和 p 的长度
        int sLen = s.size(), pLen = p.size();

        // 如果 s 的长度小于 p 的长度，返回空的结果
        if (sLen < pLen)
        {
            return vector<int>();
        }

        // 用于存放异位词起始索引的结果
        vector<int> ans;
        // 用于记录当前窗口内字符的频率
        vector<int> sCount(26, 0);
        // 用于记录字符串 p 中字符的频率
        vector<int> pCount(26, 0);

        // 统计字符串 p 中每个字符的频率
        for (int i = 0; i < pLen; ++i)
        {
            // 将字符 p 中的频率填入 pCount
            ++pCount[p[i] - 'a'];
            // 将字符 s 中的前 pLen 个字符的频率填入 sCount
            ++sCount[s[i] - 'a'];
        }

        // 比较初始窗口（s 的前 pLen 个字符）与 p 的字符频率是否相同
        if (sCount == pCount)
        {
            ans.emplace_back(0); // 如果相同，记录起始索引 0
        }

        // 开始滑动窗口
        for (int i = 0; i < sLen - pLen; ++i)
        {
            // 移除当前窗口左侧的字符（s[i]）
            --sCount[s[i] - 'a'];
            // 添加当前窗口右侧的新字符（s[i + pLen]）
            ++sCount[s[i + pLen] - 'a'];

            // 当窗口大小等于 p 的长度时，比较字符频率
            if (sCount == pCount)
            {
                ans.emplace_back(i + 1); // 如果相同，记录起始索引（i + 1）
            }
        }

        // 返回所有找到的异位词起始索引
        return ans;
    }
};

// 560. 和为 K 的子数组
// ways1:枚举   无法通过，超时
class Solution
{
public:
    int subarraySum(vector<int> &nums, int k)
    {
        int count = 0;
        for (int start = 0; start < nums.size(); ++start)
        {
            int sum = 0;
            for (int end = start; end >= 0; --end)
            {
                sum += nums[end];
                if (sum == k)
                {
                    count++;
                }
            }
        }
        return count;
    }
};

// way2：前缀和+哈希表优化
class Solution
{
public:
    int subarraySum(vector<int> &nums, int k)
    {
        unordered_map<int, int> mp; // 哈希表，存储前缀和出现的次数
        mp[0] = 1;                  // 初始化前缀和为0的出现次数为1
        int count = 0;              // 记录满足条件的子数组个数
        int pre = 0;                // 累加计算前缀和

        // 遍历数组中的每个元素
        for (auto &x : nums)
        {
            pre += x; // 更新前缀和
            // 判断是否存在 pre[i] - k 的前缀和
            if (mp.find(pre - k) != mp.end())
            {
                count += mp[pre - k]; // 将符合条件的前缀和的次数加入到结果
            }
            mp[pre]++; // 更新当前前缀和在哈希表中的出现次数
        }

        return count; // 返回满足条件的子数组个数
    }
};

// ways2:前缀和+哈希表优化

链表
160.相交链表

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        int LenA = 0;
        int LenB = 0;
        ListNode *p1 = headA;
        ListNode *p2 = headB;
        while (p1)
        {
            LenA++;
            p1 = p1->next;
        }
        while (p2)
        {
            LenB++;
            p2 = p2->next;
        }
        p1 = headA;
        p2 = headB;
        if (LenA > LenB)
        {
            for (int i = 0; i < LenA - LenB; i++)
            {
                p1 = p1->next; // 不能用p1++;
            }
        }
        else
        {
            for (int i = 0; i < LenB - LenA; i++)
            {
                p2 = p2->next;
            }
        }
        while (p1 && p2)
        {
            if (p1 == p2)
            {
                return p1;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return nullptr;
    }
};

206. 反转链表 class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        // 递归终止条件：如果当前节点为空或仅有一个节点，则返回该节点。
        // 这是因为单个节点或空链表不需要反转，直接返回自己即可。
        if (!head || !head->next)
        {
            return head;
        }

        // 递归调用：将当前节点的下一个节点作为新的头节点递归调用
        // 用 newHead 保存整个反转后的链表头节点
        ListNode *newHead = reverseList(head->next);

        // 反转过程：将当前节点的下一个节点的 next 指向当前节点
        // 也就是说，当前节点 head 成为 head->next 节点的后继节点，从而完成局部反转
        head->next->next = head;

        // 断开当前节点与下一个节点的连接
        // 这样可以确保链表不会形成环，并且所有节点都重新连接到新反转的方向上
        head->next = nullptr;

        // 返回新的链表头节点，这个头节点在递归的过程中最终会返回到最上层
        return newHead;
    }
};

234. 回文链表

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;         // 节点的值
     *     ListNode *next;  // 指向下一个节点的指针
     *     ListNode() : val(0), next(nullptr) {}  // 默认构造函数，初始化值为0，next为nullptr
     *     ListNode(int x) : val(x), next(nullptr) {}  // 构造函数，初始化值为x，next为nullptr
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}  // 构造函数，初始化值为x，next指向下一个节点
     * };
     */

    class Solution
{
public:
    // 判断链表是否为回文链表
    bool isPalindrome(ListNode *head)
    {
        vector<int> arr1;     // 用于存储链表中的值
        ListNode *cur = head; // 当前节点指针，初始指向链表头部

        // 将链表中的元素依次存入 arr1 中
        while (cur != nullptr) // 注意：这里判断 cur 是否为 nullptr，避免错误访问链表末尾
        {
            arr1.push_back(cur->val); // 将当前节点的值加入到数组中
            cur = cur->next;          // 指向下一个节点
        }

        // 判断数组 arr1 是否是回文的
        for (int i = 0, j = (int)arr1.size() - 1; i < j; i++, j--)
        { // 使用双指针法，i从左向右，j从右向左
            if (arr1[i] != arr1[j])
            {                 // 如果左右两边的元素不相等，说明不是回文链表
                return false; // 直接返回 false
            }
        }

        // 如果左右两边的元素都相等，则说明是回文链表
        return true;
    }
};

141. 环形链表
    快慢指针法 struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        // 步骤1: 初始化两个指针
        ListNode *slow = head, *fast = head;

        // 步骤2: 判断是否存在环
        while (fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;       // 慢指针走一步
            fast = fast->next->next; // 快指针走两步

            if (slow == fast)
            { // 如果相遇，说明有环
                // 步骤3: 找到环的入口点
                slow = head; // 慢指针从头开始
                while (slow != fast)
                { // 两个指针同步移动
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow; // 返回环的入口点
            }
        }

        // 如果fast指针走到了链表末尾，说明没有环
        return nullptr;
    }
};

哈希表：
class Solution
{
public:
    bool hasCycle(ListNode *head)
    {
        // 用set,存储不重复的元素
        unordered_set<ListNode *> seen;

        while (head != nullptr)
        {
            // 如果该节点已经存在哈希表中，说明该链表是环形链表
            if (seen.count(head))
            {
                return true;
            }
            // 否则就讲该节点加入哈希表中
            seen.insert(head);
            head = head->next;
        }
        return false;
    }
};

142. 环形链表 II
    快慢指针法 class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        unordered_set<ListNode *> visited;
        while (head != nullptr)
        {
            if (visited.count(head))
            {
                return head;
            }
            visited.insert(head);
            head = head->next;
        }
        return nullptr;
    }
};
哈希表：
class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        // 用于存储已访问的节点指针
        unordered_set<ListNode *> visited;

        // 遍历链表
        while (head != nullptr)
        {
            // 如果当前节点已经存在于哈希表中，说明找到了环的入口
            if (visited.count(head))
            {
                return head; // 返回环的入口节点
            }
            // 如果当前节点不在哈希表中，将其插入
            visited.insert(head);
            // 移动到下一个节点
            head = head->next;
        }

        // 遍历结束后，如果没有环，则返回 nullptr
        return nullptr;
    }
};

21. 合并两个有序链表

    递归 class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        // 如果 l1 为空，返回 l2
        if (l1 == nullptr)
        {
            return l2;
        }
        // 如果 l2 为空，返回 l1
        else if (l2 == nullptr)
        {
            return l1;
        }
        // 如果 l1 当前节点值小于 l2 当前节点值
        else if (l1->val < l2->val)
        {
            // 递归合并 l1 的下一个节点与 l2
            l1->next = mergeTwoLists(l1->next, l2);
            return l1; // 返回当前 l1 作为新链表的头节点
        }
        // 如果 l2 当前节点值大于等于 l1 当前节点值
        else
        {
            // 递归合并 l1 与 l2 的下一个节点
            l2->next = mergeTwoLists(l1, l2->next);
            return l2; // 返回当前 l2 作为新链表的头节点
        }
    }
};

迭代（循环）
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        // 创建一个虚拟头节点用于简化操作
        ListNode *prevHead = new ListNode(-1);
        ListNode *prev = prevHead; // prev指向当前合并链表的尾部

        // 遍历两个链表，直到其中一个为空
        while (l1 != nullptr && l2 != nullptr)
        {
            if (l1->val < l2->val)
            {
                prev->next = l1; // 将l1当前节点链接到prev的后面
                l1 = l1->next;   // l1指针向后移动
            }
            else
            {
                prev->next = l2; // 将l2当前节点链接到prev的后面
                l2 = l2->next;   // l2指针向后移动
            }
            prev = prev->next; // prev指针向后移动
        }

        // 将剩余的链表连接到合并链表末尾
        if (l1 == nullptr)
        {
            prev->next = l2; // 如果l1为空，直接将l2剩余部分接到后面
        }
        else
        {
            prev->next = l1; // 如果l2为空，直接将l1剩余部分接到后面
        }

        return prevHead->next; // 返回合并后的链表，跳过伪头节点
    }
};

2.两数相加

    while (l1 != nullptr || l2 != nullptr || carry != 0)
{                    // 当至少一个链表未遍历或有进位时继续循环
    int sum = carry; // 开始的和为进位
    if (l1 != nullptr)
    { // 如果 l1 指针不为空，添加它的值
        sum += l1->val;
        l1 = l1->next;
    }
    if (l2 != nullptr)
    { // 如果 l2 指针不为空，添加它的值
        sum += l2->val;
        l2 = l2->next;
    }

    carry = sum / 10;                       // 更新进位
    current->next = new ListNode(sum % 10); // 当前节点取余数作为个位数
    current = current->next;                // 移动到下一个节点
}

return dummyHead->next; // 返回新链表的头节点，跳过哨兵节点

24. 两两交换链表中的节点
    递归 class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        // 1. 递归终止条件：链表为空或只有一个节点，直接返回头节点
        if (head == nullptr || head->next == nullptr)
        {
            return head;
        }

        // 2. 当前节点的下一个节点将成为新的头节点
        ListNode *newhead = head->next;

        // 3. 递归处理后续链表，并将结果接到当前节点的 next 上
        head->next = swapPairs(newhead->next);

        // 4. 交换当前两个节点
        newhead->next = head;

        // 5. 返回交换后的新头节点
        return newhead;
    }
};

迭代
class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        // 哨兵节点，简化操作
        ListNode *dummy = new ListNode(0, head);
        ListNode *prev = dummy; // 指向要交换的前一个节点

        // 遍历链表，每次处理两个节点
        while (prev->next != nullptr && prev->next->next != nullptr)
        {
            ListNode *node1 = prev->next;       // 第一个节点
            ListNode *node2 = prev->next->next; // 第二个节点

            // 调整指针，完成两两交换
            prev->next = node2;        // 前一个节点指向第二个节点
            node1->next = node2->next; // 第一个节点指向第二个节点的后继
            node2->next = node1;       // 第二个节点指向第一个节点

            // 将 prev 移动到 node1，准备下一组交换
            prev = node1;
        }

        ListNode *newHead = dummy->next; // 新链表的头节点
        delete dummy;                    // 释放哨兵节点
        return newHead;
    }
};

138. 随机链表的复制

    /*
    // Definition for a Node.
    class Node {
    public:
        int val;
        Node* next;
        Node* random;

        Node(int _val) {
            val = _val;
            next = NULL;
            random = NULL;
        }
    };
    */

    class Solution
{
public:
    Node *copyRandomList(Node *head)
    {
        // 哈希表用于存储原节点和新节点的映射
        map<Node *, Node *> nodeMap;

        // 初始化拷贝链表的头和尾指针
        Node *copyhead = nullptr;
        Node *copytail = nullptr;

        // 遍历原链表，复制节点并建立节点映射
        Node *cur = head;
        while (cur)
        {
            // 如果拷贝链表为空，初始化头节点
            // 一开始的情况
            if (copytail == nullptr)
            {
                copyhead = copytail = new Node(cur->val);
            }
            else
            { // 如果不为空，创建新节点并接到拷贝链表末尾
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            // 将原节点和新节点存储到哈希表中
            nodeMap[cur] = copytail;
            cur = cur->next; // 移动到下一个原链表节点
        }

        // 第二次遍历原链表，复制 random 指针
        cur = head;
        Node *copy = copyhead; // copy 用于遍历拷贝链表
        while (cur)
        {
            // 若 cur 的 random 指针为空，则 copy 的 random 也为空
            if (cur->random == nullptr)
            {
                copy->random = nullptr;
            }
            else
            {
                // 若 cur 的 random 指向某个节点，则通过 nodeMap 获取对应的拷贝节点
                copy->random = nodeMap[cur->random];
            }
            // 继续遍历原链表和拷贝链表
            cur = cur->next;
            copy = copy->next;
        }

        // 返回拷贝链表的头节点
        return copyhead;
    }
};

拼接 + 拆分 class Solution
{
public:
    Node *copyRandomList(Node *head)
    {
        if (head == nullptr)
            return nullptr;
        Node *cur = head;
        // 1. 复制各节点，并构建拼接链表
        while (cur != nullptr)
        {
            Node *tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }
        // 2. 构建各新节点的 random 指向
        cur = head;
        while (cur != nullptr)
        {
            if (cur->random != nullptr)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        // 3. 拆分两链表
        cur = head->next;
        Node *pre = head, *res = head->next;
        while (cur->next != nullptr)
        {
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = nullptr; // 单独处理原链表尾节点
        return res;          // 返回新链表头节点
    }
};

147. 对链表进行插入排序
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
    class Solution
{
public:
    ListNode *insertionSortList(ListNode *head)
    {
        if (head == nullptr)
        {
            return nullptr;
        }
        ListNode *dummyHead = new ListNode(-1);
        dummyHead->next = head;
        ListNode *lastSorted = head, *cur = head->next;

        while (cur != nullptr)
        {
            // 说明 curr 应该位于 lastSorted 之后，将 lastSorted 后移一位，curr 变成新的 lastSorted。
            if (lastSorted->val <= cur->val)
            {
                lastSorted = lastSorted->next;
            }
            else
            {
                // ，从链表的头节点开始往后遍历链表中的节点，寻找插入 curr 的位置。
                ListNode *prev = dummyHead; // 待插入节点的前一个位置
                // 这里为什么用prev=head就不行？
                while (prev->next->val <= cur->val)
                {
                    prev = prev->next;
                }
                lastSorted->next = cur->next; // 5和4连
                cur->next = prev->next;       // 3和5连
                prev->next = cur;             //-1和3连
            }
            cur = lastSorted->next;
        }
        return dummyHead->next;
    }
};

148. 排序链表

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
    class Solution
{
public:
    // 主函数，入口，调用递归归并排序
    ListNode *sortList(ListNode *head)
    {
        // 传入链表头节点和空尾指针（表示链表的终止位置）
        return sortList(head, nullptr);
    }

private:
    // 递归分割和排序链表的函数
    ListNode *sortList(ListNode *head, ListNode *tail)
    {
        // 如果链表为空，直接返回
        if (head == nullptr)
        {
            return nullptr;
        }
        // 如果链表中只有一个节点
        if (head->next == tail)
        {
            // 断开链表，并返回当前节点
            head->next = nullptr;
            return head;
        }

        // 快慢指针寻找链表的中点
        ListNode *slow = head; // 慢指针
        ListNode *fast = head; // 快指针
        while (fast != tail)
        {
            slow = slow->next; // 慢指针每次移动一步
            fast = fast->next; // 快指针每次移动两步
            if (fast != tail)
            {
                fast = fast->next; // 确保快指针不会越界
            }
        }
        // 慢指针 `slow` 指向中点，链表被分为 [head, mid) 和 [mid, tail)

        // 递归处理左子链表和右子链表
        ListNode *mid = slow;
        ListNode *leftSorted = sortList(head, mid);  // 左半部分递归排序
        ListNode *rightSorted = sortList(mid, tail); // 右半部分递归排序

        // 合并两个排序后的子链表
        return Mergsort(leftSorted, rightSorted);
    }

    // 合并两个有序链表的函数
    ListNode *Mergsort(ListNode *head1, ListNode *head2)
    {
        // 创建一个虚拟头节点，便于构建新链表
        ListNode *prevHead = new ListNode(-1);
        ListNode *prev = prevHead;

        // 指针分别指向两个链表的头节点
        ListNode *l1 = head1;
        ListNode *l2 = head2;

        // 遍历两个链表，将较小的节点添加到结果链表中
        while (l1 != nullptr && l2 != nullptr)
        {
            if (l1->val < l2->val)
            {
                prev->next = l1; // 连接较小值的节点
                l1 = l1->next;   // 移动较小值链表的指针
            }
            else
            {
                prev->next = l2; // 连接较小值的节点
                l2 = l2->next;   // 移动较小值链表的指针
            }
            prev = prev->next; // 移动结果链表的指针
        }

        // 如果左链表还有剩余，连接剩余部分
        if (l1 != nullptr)
        {
            prev->next = l1;
        }
        // 如果右链表还有剩余，连接剩余部分
        if (l2 != nullptr)
        {
            prev->next = l2;
        }

        // 返回合并后的链表头节点
        return prevHead->next;
    }
};

面试题 02.04.分割链表（非leetcode100）

    class Solution
{
public:
    ListNode *partition(ListNode *head, int x)
    {
        ListNode *minhead = new ListNode(-1); // 虚拟头节点
        ListNode *maxhead = new ListNode(-1); // 虚拟头节点
        ListNode *curmin = minhead;           // 当前指向小于x的链表的尾部
        ListNode *curmax = maxhead;           // 当前指向大于等于x的链表的尾部
        ListNode *cur = head;                 // 遍历原链表

        while (cur)
        {
            if (cur->val < x)
            {
                curmin->next = cur;    // 直接连接原节点
                curmin = curmin->next; // 更新小于x链表的尾部
            }
            else
            {
                curmax->next = cur;    // 直接连接原节点
                curmax = curmax->next; // 更新大于等于x链表的尾部
            }
            cur = cur->next;
        }

        // 将大于等于x的链表的末尾指向null
        curmax->next = nullptr;
        // 将两个链表连接起来
        curmin->next = maxhead->next;

        // 返回新的链表头，跳过虚拟头节点
        return minhead->next;
    }
};

群：每日一题
215. 数组中的第K个最大元素

    自带的函数 class Solution
{
public:
    int findKthLargest(vector<int> &nums, int k)
    {
        priority_queue<int> pq(nums.begin(), nums.end());
        while (--k) //--k执行k-1次
        {
            pq.pop();
        }
        return pq.top();
    }
};

快速选择
class Solution
{
public:
    int quickselect(vector<int> &nums, int l, int r, int k)
    {
        if (l == r)
            return nums[k];
        int partition = nums[l], i = l - 1, j = r + 1;
        while (i < j)
        {
            do
                i++;
            while (nums[i] < partition);
            do
                j--;
            while (nums[j] > partition);
            if (i < j)
                swap(nums[i], nums[j]);
        }
        if (k <= j)
            return quickselect(nums, l, j, k);
        else
            return quickselect(nums, j + 1, r, k);
    }

    int findKthLargest(vector<int> &nums, int k)
    {
        int n = nums.size();
        return quickselect(nums, 0, n - 1, n - k);
    }
};

129. 求根节点到叶节点数字之和

    class Solution
{
public:
    int dfs(TreeNode *root, int prevSum)
    {
        if (root == nullptr)
        {
            return 0;
        }
        int sum = prevSum * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr)
        {
            return sum;
        }
        else
        {
            return dfs(root->left, sum) + dfs(root->right, sum);
        }
    }
    int sumNumbers(TreeNode *root)
    {
        return dfs(root, 0);
    }
};
// dfs
class Solution
{
public:
    int sumNumbers(TreeNode *root)
    {
        return dfs(root, 0); // 从根节点开始递归，当前路径数字从 0 开始
    }

    int dfs(TreeNode *node, int current_sum)
    {
        if (!node)
            return 0; // 如果当前节点为空，返回 0

        // 当前路径上的数字
        current_sum = current_sum * 10 + node->val;

        // 如果是叶子节点，返回当前路径的数字
        if (!node->left && !node->right)
        {
            return current_sum;
        }

        // 递归左右子树，计算总和
        return dfs(node->left, current_sum) + dfs(node->right, current_sum);
    }
};

// 回溯

112. 路径总和
    // dfs
    class Solution
{
public:
    bool traversal(TreeNode *cur, int count) // 注意函数的返回类型
    {
        // 到了叶子节点，count 为 0，此路径符合条件
        if (cur->left == nullptr && !cur->right && count == 0)
        {
            return true;
        }

        // 如果当前节点不是叶子节点且子节点为空，则返回 false
        if (!cur->left && cur->right == nullptr)
        {
            return false;
        }

        // 如果当前节点有左子节点
        if (cur->left)
        {
            count -= cur->left->val;         // 将目标和减去当前节点的值
            if (traversal(cur->left, count)) // 递归左子树
                return true;
            count += cur->left->val; // 回溯，撤销对 count 的改变
        }

        // 如果当前节点有右子节点
        if (cur->right)
        {
            count -= cur->right->val;         // 将目标和减去当前节点的值
            if (traversal(cur->right, count)) // 递归右子树
                return true;
            count += cur->right->val; // 回溯，撤销对 count 的改变
        }

        return false; // 如果左右子树都没有找到符合条件的路径，返回 false
    }

    bool hasPathSum(TreeNode *root, int targetSum)
    {
        if (root == nullptr)
            return false;
        return traversal(root, targetSum - root->val);
    }
};

// 精简后
class Solution
{
public:
    bool hasPathSum(TreeNode *root, int targetSum)
    {
        // 如果当前节点为空，则返回false
        if (root == nullptr)
        {
            return false;
        }

        // 如果是叶子节点且目标和等于当前节点的值，返回true
        if (!root->left && !root->right && targetSum == root->val)
        {
            return true;
        }

        // 递归检查左子树和右子树，并减少目标和
        return hasPathSum(root->left, targetSum - root->val) ||
               hasPathSum(root->right, targetSum - root->val);
    }
};
// 迭代
class Solution
{
public:
    bool hasPathSum(TreeNode *root, int sum)
    {
        // 如果根节点为空，直接返回false
        if (root == nullptr)
            return false;

        // 栈，用于模拟递归，存储的是pair<节点指针，路径数值>
        stack<pair<TreeNode *, int>> st;

        // 将根节点及其路径值（root->val）压入栈中
        st.push(pair<TreeNode *, int>(root, root->val));

        // 使用栈模拟前序遍历
        while (!st.empty())
        {
            // 获取栈顶元素
            pair<TreeNode *, int> node = st.top();
            st.pop();

            // 如果当前节点是叶子节点且路径和等于sum，返回true
            if (!node.first->left && !node.first->right && sum == node.second)
            {
                return true;
            }

            // 如果当前节点有右子节点，压入栈，并更新路径数值
            if (node.first->right)
            {
                st.push(pair<TreeNode *, int>(node.first->right, node.second + node.first->right->val));
            }

            // 如果当前节点有左子节点，压入栈，并更新路径数值
            if (node.first->left)
            {
                st.push(pair<TreeNode *, int>(node.first->left, node.second + node.first->left->val));
            }
        }

        // 如果遍历完成后没有找到符合条件的路径，返回false

        113. 路径总和 II class Solution
        {
        private:
            vector<vector<int>> result; // 结果数组
            vector<int> path;           // 单条路径数组
            void traversal(TreeNode *cur, int count)
            {
                if (!cur->left && !cur->right && count == 0)
                {
                    result.push_back(path); // 此条路径符合，加入。
                    return;
                }
                if (!cur->left && !cur->right)
                    return;
                if (cur->left)
                {
                    path.push_back(cur->left->val);
                    count -= cur->left->val;
                    traversal(cur->left, count); // 递归
                    count += cur->left->val;     // 能走到这步说明不符合要求，回溯
                    path.pop_back();             // 回溯
                }
                if (cur->right)
                {
                    path.push_back(cur->right->val);
                    count -= cur->right->val;
                    traversal(cur->right, count); // 递归
                    count += cur->right->val;     // 回溯
                    path.pop_back();              // 回溯
                }
                return;
            }

        public:
            vector<vector<int>> pathSum(TreeNode *root, int targetSum)
            {
                result.clear();
                path.clear();
                if (root == nullptr)
                    return result;
                path.push_back(root->val);
                traversal(root, targetSum - root->val);
                return result;
            }
        };

        572. 另一棵树的子树 class Solution
        {
        public:
            bool check(TreeNode *o, TreeNode *t)
            {
                if (!o && !t)
                {
                    return true;
                }
                if ((o && !t) || (!o && t) || (o->val != t->val))
                {
                    return false;
                }
                return check(o->left, t->left) && check(o->right, t->right);
            }

            bool dfs(TreeNode *o, TreeNode *t)
            {
                if (!o)
                {
                    return false;
                }
                return check(o, t) || dfs(o->left, t) || dfs(o->right, t);
            }

            bool isSubtree(TreeNode *s, TreeNode *t)
            {
                return dfs(s, t);
            }
        };

        2697. 字典序最小回文串
            双指针 class Solution
        {
        public:
            string makeSmallestPalindrome(string s)
            {
                int left = 0, right = s.size() - 1;
                while (left < right)
                {
                    if (s[left] != s[right])
                    {
                        s[left] = s[right] = min(s[left], s[right]);
                    }
                    ++left;
                    --right;
                }
                return s;
            }
        };

        class Solution
        {
        public:
            string makeSmallestPalindrome(string s)
            {
                int i = 0, j = s.size() - 1;
                while (i < j)
                {
                    if (s[i] != s[j])
                    {
                        if (s[i] < s[j])
                        {
                            s[j] = s[i];
                        }
                        else
                        {
                            s[i] = s[j];
                        }
                    }
                    i++;
                    j--;
                }
                return s;
            }
        };

        283. 移动零 class Solution
        {
        public:
            void moveZeroes(vector<int> &nums)
            {
                int n = nums.size(); // 获取数组的大小
                int left = 0;        // 初始化左指针，从头开始
                int right = 0;       // 初始化右指针，从头开始

                while (right < n)
                { // 遍历数组，直到右指针到达数组末尾
                    if (nums[right] != 0)
                    {                                  // 如果右指针指向的元素不是 0
                        swap(nums[left], nums[right]); // 交换左右指针指向的元素
                        left++;                        // 左指针右移，表示已经处理了一个非零元素
                    }
                    right++; // 无论右指针指向的元素是不是 0，右指针都向右移动
                }
            }
        };

        961. 在长度 2N 的数组中找出重复 N 次的元素 class Solution
        {
        public:
            int repeatedNTimes(vector<int> &nums)
            {
                unordered_set<int> found;
                for (int num : nums)
                {
                    if (found.count(num))
                    {
                        return num;
                    }
                    found.insert(num);
                }
                // 不可能的情况
                return -1;
            }
        };

        class Solution
        {
        public:
            int repeatedNTimes(vector<int> &nums)
            {
                unordered_map<int, int> map;
                int n = 0;
                int res = 0;
                for (auto e : nums)
                {
                    map[e]++;
                    n++;
                }
                for (auto e : map)
                {
                    if (e.second == n / 2)
                    {
                        res = e.first;
                    }
                }
                return res;
            }
        };

        350. 两个数组的交集 II
            // 哈希表O(M+N)
            class Solution
        {
        public:
            vector<int> intersect(vector<int> &nums1, vector<int> &nums2)
            {
                if (nums1.size() > nums2.size())
                {
                    return intersect(nums2, nums1);
                }
                unordered_map<int, int> m;
                for (int num : nums1)
                {
                    ++m[num];
                }
                vector<int> intersection;
                for (int num : nums2)
                {
                    if (m.count(num))
                    {
                        intersection.push_back(num);
                        --m[num];
                        if (m[num] == 0)
                        {
                            m.erase(num);
                        }
                    }
                }
                return intersection;
            }
        };
        // 排序+双指针
        class Solution
        {
        public:
            vector<int> intersect(vector<int> &nums1, vector<int> &nums2)
            {
                sort(nums1.begin(), nums1.end());
                sort(nums2.begin(), nums2.end());
                vector<int> res;
                int i = 0, j = 0;
                // 1 1 2 2
                // 2 2
                int len1 = nums1.size(), len2 = nums2.size();
                while (i < len1 && j < len2)
                {
                    if (nums1[i] == nums2[j])
                    {
                        res.push_back(nums1[i]);
                        i++;
                        j++;
                    }
                    else
                    {
                        if (nums1[i] > nums2[j])
                            j++;
                        else
                            i++;
                    }
                }
                return res;
            }
        };

        // O(m*n)
        class Solution
        {
        public:
            vector<int> intersect(vector<int> &nums1, vector<int> &nums2)
            {
                vector<int> res;
                for (int i = 0; i < nums1.size(); i++)
                {
                    for (int j = 0; j < nums2.size(); j++)
                    {
                        if (nums1[i] == nums2[j])
                        {
                            res.push_back(nums1[i]);
                            nums2.erase(nums2.begin() + j);
                            break;
                        }
                    }
                }
                return res;
            }
        };

        217. 存在重复元素 class Solution
        {
        public:
            bool containsDuplicate(vector<int> &nums)
            {
                sort(nums.begin(), nums.end());
                int n = nums.size();
                for (int i = 0; i < n - 1; i++)
                {
                    if (nums[i] == nums[i + 1])
                    {
                        return true;
                    }
                }
                return false;
            }
        };

        884. 两句话中的不常见单词 class Solution
        {
        public:
            vector<string> uncommonFromSentences(string s1, string s2)
            {
                // 创建哈希表存储每个单词及其出现次数
                unordered_map<string, int> mp;
                // 创建结果数组，用于存储不常见单词
                vector<string> res;

                // 创建两个字符串流对象，用于处理两个句子
                stringstream a, b;

                // 用于临时存储从流中读取的单词
                string s;

                // 将两个句子分别写入对应的字符串流中
                a << s1; // 第一个句子写入流a
                b << s2; // 第二个句子写入流b

                // 处理第一个句子：从流a中读取单词并统计
                // a >> s 会自动按空格分割单词，每次读取一个单词到s中
                // 如果读取成功返回true，读到末尾返回false
                while (a >> s)
                {
                    mp[s]++; // 将当前单词的出现次数加1
                }

                // 处理第二个句子：从流b中读取单词并统计
                while (b >> s)
                {
                    mp[s]++; // 将当前单词的出现次数加1
                }

                // 遍历哈希表，找出只出现一次的单词
                // auto m 中 m.first 是单词，m.second 是出现次数
                for (auto m : mp)
                {
                    // 如果单词只出现一次，说明它是不常见单词
                    if (m.second == 1)
                    {
                        res.push_back(m.first); // 将这个单词加入结果数组
                    }
                }

                return res; // 返回所有不常见单词
            }
        };

        // 我写的
        class Solution
        {
        public:
            vector<string> uncommonFromSentences(string s1, string s2)
            {
                vector<string> words1, words2;
                string word;

                // 处理第一个句子
                for (auto e1 : s1)
                {
                    if (e1 == ' ')
                    {
                        if (!word.empty())
                        {
                            words1.push_back(word);
                            word.clear();
                        }
                    }
                    else
                    {
                        word += e1;
                    }
                }
                // 处理第一个句子的最后一个单词
                if (!word.empty())
                {
                    words1.push_back(word);
                    word.clear(); // 清空word，准备处理第二个句子
                }

                // 处理第二个句子
                for (auto e1 : s2)
                {
                    if (e1 == ' ')
                    {
                        if (!word.empty())
                        {
                            words2.push_back(word);
                            word.clear();
                        }
                    }
                    else
                    {
                        word += e1;
                    }
                }
                // 处理第二个句子的最后一个单词
                if (!word.empty())
                {
                    words2.push_back(word);
                }

                // 统计词频
                unordered_map<string, int> map1;
                unordered_map<string, int> map2;
                for (auto e : words1)
                {
                    map1[e]++;
                }
                for (auto e : words2)
                {
                    map2[e]++; // 这里改用map2
                }

                // 查找不常见单词
                vector<string> res;
                // 遍历第一个map，找在s1中出现一次且在s2中未出现的单词
                for (const auto &pair : map1)
                {
                    if (pair.second == 1 && map2.find(pair.first) == map2.end())
                    {
                        res.push_back(pair.first);
                    }
                }
                // 遍历第二个map，找在s2中出现一次且在s1中未出现的单词
                for (const auto &pair : map2)
                {
                    if (pair.second == 1 && map1.find(pair.first) == map1.end())
                    {
                        res.push_back(pair.first);
                    }
                }

                return res;
            }
        };

        class Solution
        {
        public:
            vector<string> uncommonFromSentences(string s1, string s2)
            {
                isunordered_map<string, int> freq;
                auto insert = [&](const string &s)
                {
                    stringstream ss(s);
                    string word;
                    while (ss >> word)
                    {
                        ++freq[move(word)];
                    }
                };
                insert(s1);
                insert(s2);
                vector<string> ans;
                for (const auto &[word, occ] : freq)
                {
                    if (occ == 1)
                    {
                        ans.push_back(word);
                    }
                }
                return ans; // 返回不常见单词列表
            }
        };

        136. 只出现一次的数字
            // 位运算
            class Solution
        {
        public:
            int singleNumber(vector<int> &nums)
            {
                int res = 0;
                for (int i = 0; i < nums.size(); i++)
                {
                    res ^= nums[i];
                }
                // 2 1 2 3 3
                return res;
            }
        };

        169. 多数元素 class Solution
        {
        public:
            int majorityElement(vector<int> &nums)
            {
                unordered_map<int, int> counts;
                int majority = 0, cnt = 0;
                for (int num : nums)
                {
                    ++counts[num];
                    if (counts[num] > cnt)
                    {
                        majority = num;
                        cnt = counts[num];
                    }
                }
                return majority;
            }
        };

        75. 颜色分类

            // 统计出现的次数，然后重写数组
            class Solution
        {
        public:
            void sortColors(vector<int> &nums)
            {
                map<int, int> mp;
                for (auto e : nums)
                {
                    mp[e]++;
                }
                vector<int> res;
                for (auto pair : mp)
                {
                    while (pair.second)
                    {
                        res.push_back(pair.first);
                        pair.second--;
                    }
                }
                nums = res;
            }
        };
        // 单指针
        class Solution
        {
        public:
            void sortColors(vector<int> &nums)
            {
                int n = nums.size();
                int ptr = 0;
                for (int i = 0; i < n; ++i)
                {
                    if (nums[i] == 0)
                    {
                        swap(nums[i], nums[ptr]);
                        ++ptr;
                    }
                }
                for (int i = ptr; i < n; ++i)
                {
                    if (nums[i] == 1)
                    {
                        swap(nums[i], nums[ptr]);
                        ++ptr;
                    }
                }
            }
        };

        349. 两个数组的交集 class Solution
        {
        public:
            vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
            {
                unordered_map<int, int> map1;
                unordered_map<int, int> map2;
                vector<int> res;
                for (auto e : nums1)
                {
                    map1[e]++;
                }
                for (auto e : nums2)
                {
                    map2[e]++;
                }
                for (auto pair : map1)
                {
                    if (pair.second >= 1 && map2.find(pair.first) != map2.end())
                    {
                        res.push_back(pair.first);
                    }
                }
                return res;
            }
        };

        02.05.链表求和 class Solution
        {
        public:
            ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
            {
                ListNode *dummyHead = new ListNode(0); // 用来简化链表的头节点操作
                ListNode *current = dummyHead;         // 当前节点，指向结果链表的末尾
                int carry = 0;                         // 进位

                // 遍历两个链表直到结束
                while (l1 != nullptr || l2 != nullptr || carry != 0)
                {
                    int sum = carry; // 从进位开始计算

                    // 如果l1有值，取l1的值并移动到下一个节点
                    if (l1 != nullptr)
                    {
                        sum += l1->val;
                        l1 = l1->next;
                    }

                    // 如果l2有值，取l2的值并移动到下一个节点
                    if (l2 != nullptr)
                    {
                        sum += l2->val;
                        l2 = l2->next;
                    }

                    // 计算当前位的数值和新的进位
                    carry = sum / 10;                       // 进位
                    current->next = new ListNode(sum % 10); // 当前位的值
                    current = current->next;                // 移动到新的末尾节点
                }

                // 返回结果链表的头节点（跳过dummyHead）
                return dummyHead->next;
            }
        };
        704.二分查找 class Solution
        {
        public:
            int search(vector<int> &nums, int target)
            {
                int i = 0, j = nums.size() - 1;
                while (i <= j)
                {
                    int m = (i + j) / 2;
                    if (nums[m] < target)
                        i = m + 1;
                    else if (nums[m] > target)
                        j = m - 1;
                    else
                        return m;
                }
                return -1;
            }
        };
        27.移除元素 class Solution
        {
        public:
            int removeElement(vector<int> &nums, int val)
            {
                int n = nums.size();
                int left = 0;
                for (int right = 0; right < n; right++)
                {
                    if (nums[right] != val)
                    {
                        nums[left] = nums[right];
                        left++;
                    }
                }
                return left;
            }
        };
        // 69. x 的平方根
        class Solution
        {
        public:
            int mySqrt(int x)
            {
                if (x == 0)
                {
                    return 0;
                }
                int ans = exp(0.5 * log(x));
                return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
            }
        };
        397.有效的完全平方数 class Solution
        {
        public:
            bool isPerfectSquare(int num)
            {
                if (num == 0)
                {
                    return false;
                }
                long l = 1;
                long r = num;
                while (l <= r)
                {
                    long long mid = l + (r - l) / 2;
                    if (mid * mid == num)
                    {
                        return true;
                    }
                    else if (mid * mid > num)
                    {
                        r = mid - 1;
                    }
                    else
                    {
                        l = mid + 1;
                    }
                }
                return false;
            }
        };

        977.有序数组的平方 class Solution
        {
        public:
            vector<int> sortedSquares(vector<int> &nums)
            {
                for (int i = 0; i < nums.size(); i++)
                {
                    nums[i] *= nums[i];
                }
                sort(nums.begin(), nums.end());
                return nums;
            }
        };

        35. 搜索插入位置 class Solution
        {
        public:
            int searchInsert(vector<int> &nums, int target)
            {
                int left = 0, right = nums.size() - 1;
                while (left <= right)
                {
                    // 分别处理如下四种情况
                    // 目标值在数组所有元素之前  [0, -1]
                    // 目标值等于数组中某一个元素  return middle;
                    // 目标值插入数组中的位置 [left, right]，return  right + 1
                    // 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1
                    int mid = left + (right - left) / 2;
                    if (nums[mid] > target)
                    {
                        right = mid - 1;
                    }
                    else if (nums[mid] < target)
                    {
                        left = mid + 1;
                    }
                    else
                    {
                        return mid;
                    }
                }
                return right + 1;
            }
        };

        209.长度最小的子数组 class Solution
        {
        public:
            int minSubArrayLen(int s, vector<int> &nums)
            {
                int result = INT32_MAX; // 初始化结果为最大整数值，表示尚未找到满足条件的子数组
                int sum = 0;            // 滑动窗口数值之和
                int i = 0;              // 滑动窗口起始位置
                int subLength = 0;      // 滑动窗口的长度

                // 遍历数组，j 为滑动窗口的结束位置
                for (int j = 0; j < nums.size(); j++)
                {
                    sum += nums[j]; // 将当前元素加入滑动窗口的和

                    // 当滑动窗口的和大于等于目标值 s 时，尝试收缩窗口
                    while (sum >= s)
                    {
                        subLength = (j - i + 1);                          // 计算当前满足条件的子数组长度
                        result = result < subLength ? result : subLength; // 更新最小长度
                        sum -= nums[i++];                                 // 移除滑动窗口的起始元素，并将起始位置 i 向右移动
                        // 这是滑动窗口的核心操作，通过不断调整窗口的起始位置，寻找更小的满足条件的子数组
                    }
                }

                // 如果 result 仍然是初始值 INT32_MAX，说明没有找到满足条件的子数组，返回 0
                // 否则返回找到的最小长度
                return result == INT32_MAX ? 0 : result;
            }
        };

        904. 水果成篮 class Solution
        {
        public:
            int totalFruit(vector<int> &fruits)
            {
                int n = fruits.size();
                unordered_map<int, int> cnt;
                int left = 0, ans = 0;
                for (int right = 0; right < n; right++)
                {
                    ++cnt[fruits[right]];
                    while (cnt.size() > 2)
                    {
                        auto it = cnt.find(fruits[left]);
                        --it->second;
                        if (it->second == 0)
                        {
                            cnt.erase(it);
                        }
                        ++left;
                    }
                    ans = max(ans, right - left + 1);
                }
                return ans;
            }
        };

        76.最小覆盖子串 class Solution
        {
        public:
            unordered_map<char, int> tt; // 子串哈希表
            unordered_map<char, int> dd; // 当前窗口哈希表
            bool check()
            {
                for (const auto &e : tt)
                {
                    if (dd[e.first] < e.second)
                    {
                        return false;
                    }
                }
                // 当前窗口的个数满足时
                return true;
            }
            string minWindow(string s, string t)
            {
                // 初始化子串t的哈希表，
                for (const auto &c : t)
                {
                    ++tt[c];
                }
                int l = 0, r = -1;
                int len = INT_MAX, ansL = -1, ansR = -1;
                while (r < int(s.size()))
                {
                    if (tt.find(s[++r]) != tt.end())
                    {
                        dd[s[r]]++;
                    }
                    while (check() && l <= r)
                    {
                        if (r - l + 1 < len)
                        {
                            len = r - l + 1;
                            ansL = l;
                        }
                        if (tt.find(s[l]) != tt.end())
                        {
                            dd[s[l]]--;
                        }
                        l++;
                    }
                }
                return ansL == -1 ? string() : s.substr(ansL, len);
            }
        };
        59.螺旋数组 class Solution
        {
        public:
            vector<vector<int>> generateMatrix(int n)
            {
                vector<vector<int>> res(n, vector<int>(n, 0));

                int num = 1;                 // 要填充的数字，从1开始。
                int left = 0, right = n - 1; // 左右边界
                int top = 0, bottom = n - 1; // 上下边界
                // 左闭右开。

                while (num <= n * n)
                {
                    // 上横   [0,0   0,n-1)
                    for (int i = left; i <= right; i++)
                    {
                        res[top][i] = num++;
                    }
                    top++; // 上边界下移
                    // 右竖
                    for (int i = top; i <= bottom; i++)
                    {
                        res[i][right] = num++;
                    }
                    right--; // 右边界左移
                    // 下横
                    for (int i = right; i >= left; i--)
                    {
                        res[bottom][i] = num++;
                    }
                    bottom--; // 下边界上移
                    for (int i = bottom; i >= top; i--)
                    {
                        res[i][left] = num++;
                    }
                    left++; // 左边界右移
                }
                return res;
            }
        };

        54.螺旋矩阵 class Solution
        {
        public:
            vector<int> spiralOrder(vector<vector<int>> &matrix)
            {
                vector<int> res;
                if (matrix.empty() || matrix[0].empty())
                {
                    return res;
                }

                // 获取行数
                int m = matrix.size();
                // 获取列数
                int n = matrix[0].size();
                int left = 0, right = n - 1; // 左右边界
                int top = 0, bottom = m - 1; // 上下边界
                int num = 0;
                // 左闭右开。
                while (left <= right && top <= bottom)
                {
                    // 上横   [0,0   0,n-1)
                    for (int i = left; i <= right; i++)
                    {
                        res.push_back(matrix[top][i]);
                    }
                    top++; // 上边界下移
                    // 右竖
                    for (int i = top; i <= bottom; i++)
                    {
                        res.push_back(matrix[i][right]);
                    }
                    right--; // 右边界左移
                    if (top <= bottom)
                    {
                        // 下横
                        for (int i = right; i >= left; i--)
                        {
                            res.push_back(matrix[bottom][i]);
                        }
                        bottom--; // 下边界上移
                    }
                    if (left <= right)
                    {
                        for (int i = bottom; i >= top; i--)
                        {
                            res.push_back(matrix[i][left]);
                        }
                        left++; // 左边界右移
                    }
                }
                return res;
            }
        };

        LCR 146. 螺旋遍历二维数组 class Solution
        {
        public:
            vector<int> spiralArray(vector<vector<int>> &array)
            {
                vector<int> res;
                if (array.empty() || array[0].empty())
                {
                    return res;
                }
                // 获取行数
                int m = array.size();
                // 获取列数
                int n = array[0].size();
                int left = 0, right = n - 1; // 左右边界
                int top = 0, bottom = m - 1; // 上下边界
                int num = 0;
                // 左闭右开。
                while (left <= right && top <= bottom)
                {
                    // 上横   [0,0   0,n-1)
                    for (int i = left; i <= right; i++)
                    {
                        res.push_back(array[top][i]);
                    }
                    top++; // 上边界下移
                    // 右竖
                    for (int i = top; i <= bottom; i++)
                    {
                        res.push_back(array[i][right]);
                    }
                    right--; // 右边界左移
                    if (top <= bottom)
                    {
                        // 下横
                        for (int i = right; i >= left; i--)
                        {
                            res.push_back(array[bottom][i]);
                        }
                        bottom--; // 下边界上移
                    }
                    if (left <= right)
                    {
                        for (int i = bottom; i >= top; i--)
                        {
                            res.push_back(array[i][left]);
                        }
                        left++; // 左边界右移
                    }
                }
                return res;
            }
        };

        44.开发商购买土地
#include <iostream>
#include <vector>
#include <climits>
            using namespace std;

        int main()
        {
            int n, m;
            cin >> n >> m;
            vector<vector<int>> nums(n, vector<int>(m, 0));
            int sum = 0;

            // 输入矩阵并计算总和
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    cin >> nums[i][j];
                    sum += nums[i][j];
                }
            }

            // 计算每行的和
            vector<int> nsum(n, 0);
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    nsum[i] += nums[i][j];
                }
            }

            // 计算每列的和
            vector<int> msum(m, 0);
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    msum[i] += nums[j][i]; // 注意索引顺序
                }
            }

            int result = INT_MAX;

            // 横向切割
            int horizontalCut = 0;
            for (int i = 0; i < n; i++)
            {
                horizontalCut += nsum[i];
                result = min(result, abs(sum - 2 * horizontalCut));
            }

            // 纵向切割
            int verticalCut = 0;
            for (int i = 0; i < m; i++)
            {
                verticalCut += msum[i];
                result = min(result, abs(sum - 2 * verticalCut));
            }

            cout << result << endl;
            return 0;
        }

        203. 移除链表元素 class Solution
        {
        public:
            ListNode *removeElements(ListNode *head, int val)
            {
                ListNode *dummynode = new ListNode(0);
                dummynode->next = head;
                ListNode *cur = dummynode;
                while (cur->next != nullptr) //
                {
                    if (cur->next->val == val)
                    {
                        ListNode *tmp = cur->next; //
                        cur->next = cur->next->next;
                        delete tmp; //
                    }
                    else
                    {
                        cur = cur->next;
                    }
                }
                head = dummynode->next; //
                delete dummynode;       //
                return head;
            }
        };
        707. 设计链表 class MyLinkedList
        {
        public:
            struct LinkedNode
            {
                int val;
                LinkedNode *next;
                LinkedNode(int val)
                    : val(val), next(nullptr)
                {
                }
            };
            MyLinkedList()
            {
                dummynode = new LinkedNode(0);
                size = 0;
            }

            int get(int index)
            {
                // 判断下标是否合法
                if (index > (size - 1) || index < 0)
                {
                    return -1;
                }
                LinkedNode *cur = dummynode->next;
                // 1 3 4 2,index=2
                while (index--)
                { // 如果--index 就会陷入死循环
                    cur = cur->next;
                }
                return cur->val;
            }

            void addAtHead(int val)
            {
                LinkedNode *newNode = new LinkedNode(val);
                newNode->next = dummynode->next;
                dummynode->next = newNode;
                size++; // 记得更新大小。
            }

            void addAtTail(int val)
            {
                LinkedNode *newnode = new LinkedNode(val);
                LinkedNode *cur = dummynode;
                while (cur->next)
                {
                    cur = cur->next;
                }
                cur->next = newnode;
                // newnode->next=nullptr; //构造函数中，next成员已经被初始化为nullptr。因此，每当创建新节点时，next指针自动就是nullptr，无需再次设置
                size++;
            }

            // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
            // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
            // 如果index大于链表的长度，则返回空
            // 如果index小于0，则在头部插入节点
            void addAtIndex(int index, int val)
            {
                if (index > size)
                {
                    return;
                }
                if (index < 0)
                    index = 0;
                LinkedNode *newNode = new LinkedNode(val);
                LinkedNode *cur = dummynode;
                while (index--)
                {
                    cur = cur->next;
                }
                newNode->next = cur->next;
                cur->next = newNode;
                size++;
            }
            // 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
            void deleteAtIndex(int index)
            {
                if (index >= size || index < 0)
                {
                    return;
                }
                // 1 3 4- 2 5  // 2
                LinkedNode *cur = dummynode;
                while (index--)
                {
                    cur = cur->next;
                }
                // 当前在下标元素的前一个元素
                LinkedNode *tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
                // delete命令指示释放了tmp指针原本所指的那部分内存，
                // 被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
                // 如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
                // 如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
                tmp = nullptr;
                size--;
            }

        private:
            LinkedNode *dummynode;
            int size;
        };

        206. 反转链表 1.双指针 class Solution
        {
        public:
            ListNode *reverseList(ListNode *head)
            {
                ListNode *prev = nullptr;
                ListNode *curr = head;
                while (curr)
                {
                    ListNode *next = curr->next;
                    curr->next = prev;
                    prev = curr;
                    curr = next;
                }
                return prev;
            }
        };
        2.递归☆ class Solution
        {
        public:
            ListNode *reverseList(ListNode *head)
            {
                // 递归终止条件：如果当前节点为空或仅有一个节点，则返回该节点。
                // 这是因为单个节点或空链表不需要反转，直接返回自己即可。
                if (!head || !head->next)
                {
                    return head;
                }

                // 递归调用：将当前节点的下一个节点作为新的头节点递归调用
                // 用 newHead 保存整个反转后的链表头节点
                ListNode *newHead = reverseList(head->next);

                // 反转过程：将当前节点的下一个节点的 next 指向当前节点
                // 也就是说，当前节点 head 成为 head->next 节点的后继节点，从而完成局部反转
                head->next->next = head;

                // 断开当前节点与下一个节点的连接
                // 这样可以确保链表不会形成环，并且所有节点都重新连接到新反转的方向上
                head->next = nullptr;

                // 返回新的链表头节点，这个头节点在递归的过程中最终会返回到最上层
                return newHead;
            }
        };

        24. 两两交换链表中的节点
            递归

            class Solution
        {
        public:
            ListNode *swap(ListNode *prev, ListNode *cur)
            {
                if (!cur || !cur->next)
                    return cur;

                ListNode *tmp = cur->next;
                cur->next = tmp->next;
                tmp->next = cur;
                // 如果prev不为空，更新prev->next为交换后的头节点
                if (prev != nullptr)
                {
                    prev->next = tmp;
                }
                swap(cur, cur->next);
                return tmp;
            }
            ListNode *swapPairs(ListNode *head)
            {
                // 递归 or 迭代
                // 递归
                // 终止条件：
                //  创建一个虚拟头节点，方便处理头部节点交换
                ListNode *dummyHead = new ListNode(0);
                dummyHead->next = head;

                // 调用递归函数开始交换
                return swap(dummyHead, head);
            }
        };

        简化版递归
        class Solution
        {
        public:
            ListNode *swapPairs(ListNode *head)
            {
                if (head == nullptr || head->next == nullptr)
                {
                    return head;
                }
                ListNode *newHead = head->next;
                head->next = swapPairs(newHead->next);
                newHead->next = head;
                return newHead;
            }
        };

        19. 删除链表的倒数第 N 个结点

            /**
             * Definition for singly-linked list.
             * struct ListNode {
             *     int val;
             *     ListNode *next;
             *     ListNode() : val(0), next(nullptr) {}
             *     ListNode(int x) : val(x), next(nullptr) {}
             *     ListNode(int x, ListNode *next) : val(x), next(next) {}
             * };
             */
            class Solution
        {
        public:
            ListNode *removeNthFromEnd(ListNode *head, int n)
            {
                // 创建虚拟头节点，便于处理头节点删除的情况
                ListNode *dummyNode = new ListNode(0);
                dummyNode->next = head; // 虚拟头节点指向原始头节点

                ListNode *cur = dummyNode;
                int size = 0;

                // 计算链表的长度
                while (cur->next)
                {
                    size++;
                    cur = cur->next;
                }

                // 重新从虚拟头节点开始，定位到倒数第n个节点的前一个节点
                cur = dummyNode;
                ListNode *prev = nullptr;
                int sum = size - n + 1;
                while (sum--)
                {
                    prev = cur;
                    cur = cur->next;
                }
                // 1 2 3 4 5,删除4，倒数第二个
                // size-n+1=5-2+1 =4次，cur跳四次才到删除的位置

                // 现在 prev 是倒数第n个节点的前一个节点，cur 是倒数第n个节点
                // 删除倒数第n个节点
                if (prev != nullptr && cur != nullptr)
                {
                    prev->next = cur->next; // 删除目标节点
                    delete cur;             // 释放节点内存
                }

                // 返回新的链表头
                ListNode *result = dummyNode->next;
                delete dummyNode; // 释放虚拟头节点的内存
                return result;
            }
        };

        面试题 02.07.链表相交
            /**
             * Definition for singly-linked list.
             * struct ListNode {
             *     int val;
             *     ListNode *next;
             *     ListNode(int x) : val(x), next(NULL) {}
             * };
             */
            class Solution
        {
        public:
            ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
            {
                int lenA = 0, lenB = 0;
                ListNode *curA = headA;
                ListNode *curB = headB;
                while (curA)
                {
                    lenA++;
                    curA = curA->next;
                }
                while (curB)
                {
                    lenB++;
                    curB = curB->next;
                }
                curA = headA;
                curB = headB;
                if (lenA > lenB)
                {
                    int n = lenA - lenB;
                    while (n--)
                    {
                        curA = curA->next;
                    }
                }
                else
                {
                    int n = lenB - lenA;
                    curB = headB;
                    while (n--)
                    {
                        curB = curB->next;
                    }
                }
                while (curA)
                {
                    if (curA == curB)
                    {
                        return curA;
                    }
                    curA = curA->next;
                    curB = curB->next;
                }
                return NULL;
            }
        };

        42. 环形链表 II class Solution
        {
        public:
            ListNode *detectCycle(ListNode *head)
            {
                unordered_set<ListNode *> visited;
                while (head != nullptr)
                {
                    if (visited.count(head))
                    {
                        return head;
                    }
                    visited.insert(head);
                    head = head->next;
                }
                return nullptr;
            }
        };

        242. 有效的字母异位词

            class Solution
        {
        public:
            bool isAnagram(string s, string t)
            {
                int num[26] = {0};
                for (int i = 0; i < s.size(); i++)
                {
                    num[s[i] - 'a']++;
                }
                for (int i = 0; i < t.size(); i++)
                {
                    num[t[i] - 'a']--;
                }
                for (int i = 0; i < 26; i++)
                {
                    if (num[i] != 0)
                    {
                        return false;
                    }
                }
                return true;
            }
        };

        349. 两个数组的交集 class Solution
        {
        public:
            vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
            {
                unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
                unordered_set<int> nums_set(nums1.begin(), nums1.end());
                for (int num : nums2)
                {
                    // 发现nums2的元素 在nums_set里又出现过
                    if (nums_set.find(num) != nums_set.end())
                    {
                        result_set.insert(num);
                    }
                }
                return vector<int>(result_set.begin(), result_set.end());
            }
        };

        202. 快乐数 class Solution
        {
        public:
            // 取数值各个位上的单数之和
            int getSum(int n)
            {
                int sum = 0;
                while (n)
                {
                    sum += (n % 10) * (n % 10);
                    n /= 10;
                }
                return sum;
            }
            bool isHappy(int n)
            {
                unordered_set<int> set;
                while (1)
                {
                    int sum = getSum(n);
                    if (sum == 1)
                    {
                        return true;
                    }
                    // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
                    if (set.find(sum) != set.end())
                    {
                        return false;
                    }
                    else
                    {
                        set.insert(sum);
                    }
                    n = sum;
                }
            }
        };

        1. 两数之和 class Solution
        {
        public:
            vector<int> twoSum(vector<int> &nums, int target)
            {
                unordered_map<int, int> map1;
                vector<int> res;
                for (int i = 0; i < nums.size(); i++)
                {
                    // 看看差的那个数是否在map,如果在则加入结果
                    if (map1.find(target - nums[i]) != map1.end())
                    {
                        return {map1.find(target - nums[i])->second, i};
                    }
                    map1.insert(pair<int, int>(nums[i], i));
                }
                return {};
            }
        };

        454. 四数相加 II class Solution
        {
        public:
            int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3, vector<int> &nums4)
            {
                int res = 0; // 结果
                unordered_map<int, int> ab;
                for (auto a : nums1)
                {
                    for (auto b : nums2)
                    {
                        ab[a + b]++;
                    }
                }
                for (auto c : nums3)
                {
                    for (auto d : nums4)
                    {
                        if (ab.find(0 - (c + d)) != ab.end())
                        {
                            res += ab[0 - (c + d)];
                            // 注意这里,直接加上ab[0-(c+d)]。
                            // 假如此次c+d=2，那么ab里得有一个-2,这里的-2可能是1+-3，可能是-1+-1.
                        }
                    }
                }
                return res;
            }
        };

        383. 赎金信 class Solution
        {
        public:
            bool canConstruct(string ransomNote, string magazine)
            {
                unordered_map<int, int> map;
                for (auto e : magazine)
                {
                    map[e]++;
                }
                for (auto e : ransomNote)
                {
                    map[e]--;
                    if (map[e] < 0)
                    {
                        return false;
                    }
                }
                return true;
            }
        };

        15. 三数之和

            class Solution
        {
        public:
            vector<vector<int>> threeSum(vector<int> &nums)
            {
                // 先排序
                vector<vector<int>> res;
                sort(nums.begin(), nums.end());

                // 注意读题：三元组里的元素可以重复，但是元素下标不能重复,三元组不能重复！
                //  -1,-1,2可以
                for (int i = 0; i < nums.size(); i++)
                {
                    // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
                    if (nums[i] > 0)
                    {
                        return res;
                    }
                    int left = i + 1;
                    int right = nums.size() - 1;
                    // [a, a, ...] 如果本轮a和上轮a相同，那么找到的b，c也是相同的，所以去重a
                    // 和前一个比较，若和后一个比较则漏掉了-1,-1,2的情况
                    if (i > 0 && nums[i] == nums[i - 1])
                    {
                        continue;
                    }
                    // 这里还有一个循环，切记！
                    while (right > left)
                    {
                        if (nums[i] + nums[left] + nums[right] > 0)
                        {
                            right--;
                        }
                        else if (nums[i] + nums[left] + nums[right] < 0)
                        {
                            left++;
                        }
                        else
                        {
                            res.push_back(
                                vector<int>{nums[i], nums[left], nums[right]});
                            // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                            while (right > left && nums[right] == nums[right - 1])
                                right--;
                            while (right > left && nums[left] == nums[left + 1])
                                left++;
                            // 找到答案时，双指针同时收缩
                            right--;
                            left++;
                        }
                    }
                }
                return res;
            }
        };

        18. 四数之和 class Solution
        {
        public:
            vector<vector<int>> fourSum(vector<int> &nums, int target)
            {
                // 先排序，排序有助于后续剪枝和去重
                vector<vector<int>> res;
                sort(nums.begin(), nums.end());
                int n = nums.size();
                if (n < 4)
                    return res; // 如果元素少于4个，直接返回空结果

                // 注意题目要求：四元组内的数字可以重复（如 -1,-1,2,0），
                // 但下标不能重复，且不能出现重复的四元组

                // 遍历第一个数字，范围为 0 到 n-4 (i < n-3)，因为后续还需要选3个数字
                for (int i = 0; i < n - 3; i++)
                {
                    // 跳过重复的第一个数字，防止生成重复的四元组
                    // 这里不能用 nums[i]==nums[i+1]，而应比较前一个数与当前数
                    // 这样可以保证每个数字只作为第一个数字处理一次
                    if (i > 0 && nums[i] == nums[i - 1])
                        continue;

                    // 剪枝1：如果当前第一个数字和后面三个最小数字之和大于 target，
                    // 则后续所有组合都大于 target，直接退出循环
                    if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)
                        break;
                    // 剪枝2：如果当前第一个数字与三个最大的数字之和小于 target，
                    // 则无论如何选择，和都不足 target，跳过本轮
                    if ((long)nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target)
                        continue;

                    // 固定第一个数字后，遍历第二个数字，范围为 i+1 到 n-3 (j < n-2)
                    // 因为还需要选择后面两个数字
                    for (int j = i + 1; j < n - 2; j++)
                    {
                        // 跳过重复的第二个数字，防止生成重复四元组
                        if (j > i + 1 && nums[j] == nums[j - 1])
                            continue;

                        // 剪枝3：对于固定的 i 和 j，
                        // 如果最小的四个数字之和（即当前 i, j 和后面两个最小的数字）大于 target，
                        // 则后续组合必然超出 target，直接退出当前 j 循环
                        if ((long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target)
                            break;
                        // 剪枝4：如果固定的 i 和 j 加上最大的两个数字之和仍小于 target，
                        // 则当前 i, j 无法组合出满足条件的四元组，跳过本轮
                        if ((long)nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target)
                            continue;

                        // 双指针法：初始化 left 和 right 分别指向 j+1 和数组末尾
                        int left = j + 1, right = n - 1;
                        while (left < right)
                        {
                            // 注意防止整数溢出，将计算结果转换为 long
                            long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];

                            // 如果四数之和大于 target，则当前组合过大，需要减小数值，
                            // 因为数组是有序的，所以右边的数较大，right 左移
                            if (sum > target)
                            {
                                right--;
                            }
                            // 如果四数之和小于 target，则需要增大数值，left 右移
                            else if (sum < target)
                            {
                                left++;
                            }
                            // 找到满足条件的四元组
                            else
                            {
                                res.push_back({nums[i], nums[j], nums[left], nums[right]});
                                // 去重：跳过 left 后面与当前重复的数字，防止生成重复四元组
                                while (left < right && nums[left] == nums[left + 1])
                                    left++;
                                // 去重：跳过 right 前面与当前重复的数字
                                while (left < right && nums[right] == nums[right - 1])
                                    right--;
                                // 同时移动左右指针，寻找新的组合
                                left++;
                                right--;
                            }
                        }
                    }
                }
                return res;
            }
        };

        344. 反转字符串 class Solution
        {
        public:
            void reverseString(vector<char> &s)
            {
                for (int i = 0, j = s.size() - 1; i < s.size() / 2; i++, j--)
                {
                    swap(s[i], s[j]);
                }
            }
        };
        541. 反转字符串 II class Solution
        {
        public:
            string reverseStr(string s, int k)
            {
                int n = s.size();
                for (int i = 0; i < n; i += (2 * k))
                {
                    // 1. 每隔 2k 个字符的前 k 个字符进行反转
                    // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
                    // 上面两个合在一起就是翻转每4个的后两个，因为前两个被反转了两遍。
                    if (i + k <= n) // 2k>n-i>=k  等价于 i+k<=n
                    {
                        reverse(s.begin() + i, s.begin() + i + k);
                    }
                    // 3. 剩余字符少于 k 个，则将剩余字符全部反转
                    else
                    {
                        reverse(s.begin() + i, s.end());
                    }
                }
                return s;
            }
        };

        54. 替换数字（第八期模拟笔试）

#include <bits/stdc++.h>
            using namespace std;
        int main()
        {
            string s;
            cin >> s;
            string res;
            for (int i = 0; i < s.size(); i++)
            {
                if (s[i] >= '1' && s[i] <= '9')
                {
                    res += "number";
                }
                else
                {
                    res += s[i];
                }
            }
            cout << res << endl;
            return 0;
        }
        151. 反转字符串中的单词
            解法一：双指针 class Solution
        {
        public:
            string reverseWords(string s)
            {
                // 存放结果单词
                vector<string> words;
                int i = s.size() - 1;

                while (i >= 0)
                {
                    // 1. 跳过末尾空格
                    while (i >= 0 && s[i] == ' ')
                    {
                        i--;
                    }
                    if (i < 0)
                        break; // 如果已经到达开头，结束

                    // 2. 确定当前单词的右边界 j
                    int j = i; // j 指向当前单词的末尾字符
                    // 3. 继续向左移动 i，直到遇到空格或到达字符串开头
                    while (i >= 0 && s[i] != ' ')
                    {
                        i--;
                    }
                    // 此时 s[i+1 .. j] 就是一个完整的单词
                    string word = s.substr(i + 1, j - (i + 1) + 1);
                    words.push_back(word);

                    // 4. 跳过单词间的所有空格
                    //    （上面的 while 循环退出后，i 要么是 -1，要么是空格字符）
                    //    继续循环就可以了，下一次会先跳过空格

                    // 5. 更新 j = i（在下一个循环里，j 会重新定位到下个单词末尾）
                }

                // 6. 将收集到的单词逆序拼接
                // 因为我们是从右向左收集的，words[0] 对应的是最后一个单词
                // 需要把它们逆序拼接成结果
                string result;
                for (int k = 0; k < (int)words.size(); k++)
                {
                    // 第一个单词直接拼接
                    if (k == 0)
                    {
                        result = words[k];
                    }
                    else
                    {
                        result += " " + words[k];
                    }
                }
                return result;
            }
        };
        解法二：代码随想录
        class Solution
        {
        public:
            // 辅助函数：翻转区间 [start, end] 内的字符
            void reverse(string &s, int start, int end)
            {
                for (int i = start, j = end; i < j; i++, j--)
                {
                    swap(s[i], s[j]);
                }
            }

            // 移除多余空格
            void removeExtraSpaces(string &s)
            {
                // 定义慢指针 slow，初始为 0，用于写入处理后的字符
                int slow = 0;
                // 快指针 i 遍历原字符串
                for (int i = 0; i < (int)s.size(); ++i)
                {
                    // 跳过空格，直到找到第一个非空格字符
                    if (s[i] != ' ')
                    {
                        // 如果 slow != 0，说明已经写入过一个单词，
                        // 需要在下一个单词前插入一个空格以分隔
                        if (slow != 0)
                        {
                            s[slow++] = ' ';
                        }
                        // 将当前这个单词的字符逐个写入到 s[slow..]
                        while (i < (int)s.size() && s[i] != ' ')
                        {
                            s[slow++] = s[i++];
                        }
                    }
                }
                // 处理完后，slow 即为“去除多余空格”后字符串的有效长度
                s.resize(slow);
            }

            string reverseWords(string s)
            {
                // 1. 移除多余空格：去掉首尾空格、多余空格，并只保留单个空格分隔单词
                removeExtraSpaces(s);

                // 2. 翻转整个字符串
                reverse(s, 0, s.size() - 1);

                // 3. 翻转每个单词
                int start = 0;
                for (int i = 0; i <= (int)s.size(); ++i)
                {
                    // 当 i 到达字符串末尾，或者遇到空格时，说明 [start..i-1] 是一个完整单词
                    if (i == (int)s.size() || s[i] == ' ')
                    {
                        reverse(s, start, i - 1);
                        start = i + 1; // 更新下一个单词的开始位置
                    }
                }
                return s;
            }
        };
        方法三：双端队列
        string reverseWords(string s)
        {
            int left = 0, right = s.size() - 1;
            // 1. 去掉字符串开头的空白字符
            while (left <= right && s[left] == ' ')
                ++left;

            // 2. 去掉字符串末尾的空白字符
            while (left <= right && s[right] == ' ')
                --right;

            // 定义一个双端队列，存放单词
            deque<string> d;
            // 用来收集当前扫描到的单词
            string word;

            // 3. 遍历 [left..right] 区间
            while (left <= right)
            {
                char c = s[left];
                // 遇到空格且当前已经收集到一个单词 -> 说明单词结束
                if (word.size() && c == ' ')
                {
                    // 将该单词压入队列头部
                    d.push_front(move(word));
                    word = ""; // 清空 word
                }
                // 如果不是空格，就把字符加到 word 里
                else if (c != ' ')
                {
                    word += c;
                }
                ++left;
            }
            // 循环结束后，最后一个单词还没入队
            d.push_front(move(word));

            // 4. 将队列转成结果字符串
            string ans;
            while (!d.empty())
            {
                ans += d.front(); // 取队首元素
                d.pop_front();
                if (!d.empty())
                    ans += ' '; // 单词间加空格
            }
            return ans;
        }

        右旋字符串（第八期模拟笔试）
        有三种解法
#include <iostream>
        using namespace std;
        int main()
        {
            int n;
            string s;
            cin >> n >> s;
            int len = s.size();
            cout << (s + s).substr(len - n, len) << '\n';
            return 0;
        }

        28. 找出字符串中第一个匹配项的下标(实现strStr) class Solution
        {
        public:
            void getNext(int *next, const string &s)
            {
                int j = -1;
                next[0] = j;
                for (int i = 1; i < s.size(); i++)
                { // 注意i从1开始
                    while (j >= 0 && s[i] != s[j + 1])
                    {                // 前后缀不相同了
                        j = next[j]; // 向前回退
                    }
                    if (s[i] == s[j + 1])
                    { // 找到相同的前后缀
                        j++;
                    }
                    next[i] = j; // 将j（前缀的长度）赋给next[i]
                }
            }
            int strStr(string haystack, string needle)
            {
                if (needle.size() == 0)
                {
                    return 0;
                }
                vector<int> next(needle.size());
                getNext(&next[0], needle);
                int j = -1; // // 因为next数组里记录的起始位置为-1
                for (int i = 0; i < haystack.size(); i++)
                { // 注意i就从0开始
                    while (j >= 0 && haystack[i] != needle[j + 1])
                    {                // 不匹配
                        j = next[j]; // j 寻找之前匹配的位置
                    }
                    if (haystack[i] == needle[j + 1])
                    {        // 匹配，j和i同时向后移动
                        j++; // i的增加在for循环里
                    }
                    if (j == (needle.size() - 1))
                    { // 文本串s里出现了模式串t
                        return (i - needle.size() + 1);
                    }
                }
                return -1;
            }
        };

        459. 重复的子字符串

            class Solution
        {
        public:
            bool repeatedSubstringPattern(string s)
            {
                for (int i = 0; i < s.size() - 1; i++)
                {
                    // 截取每个子串进行模拟
                    string sub = s.substr(0, i + 1);
                    // 如果 s 的长度不是 sub 的整数倍，直接跳过
                    if (s.size() % sub.size() != 0)
                        continue;
                    string word;
                    while (word.size() <= s.size())
                    {
                        // ababab
                        if (word == s)
                        {
                            return true;
                        }
                        word += sub; // 每次只加子串
                        // 比如第一次，ab, abab ,ababab,abababab
                        // 而不是     ab,  abab         abababab
                    }
                }
                return false;
            }
        };

        移动匹配
        class Solution
        {
        public:
            bool repeatedSubstringPattern(string s)
            {
                string ss = s + s;
                // 掐头去尾
                ss = ss.substr(1, ss.size() - 2);
                if (ss.find(s) != std::string::npos)
                    return true;
                return false;
            }
        };

        232. 用栈实现队列 class MyQueue
        {
        public:
            MyQueue() = default;

            void push(int x)
            {
                stin.push(x);
            }

            int pop()
            {
                // 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
                if (stout.empty())
                {
                    while (!stin.empty())
                    {
                        stout.push(stin.top());
                        stin.pop();
                    }
                }
                int res = stout.top();
                stout.pop();
                return res;
            }

            int peek()
            {
                int res = this->pop(); // 直接使用已有的pop函数
                // 注意pop也返回了要移除的元素，所以可以int res=.....
                stout.push(res); // 因为pop函数弹出了元素res，所以再添加回去
                return res;
            }

            bool empty()
            {
                return stin.empty() && stout.empty();
            }

        private:
            stack<int> stin;
            stack<int> stout;
            int top1;
        };

        /**
         * Your MyQueue object will be instantiated and called as such:
         * MyQueue* obj = new MyQueue();
         * obj->push(x);
         * int param_2 = obj->pop();
         * int param_3 = obj->peek();
         * bool param_4 = obj->empty();
         */

        225. 用队列实现栈 class MyStack
        {
        public:
            queue<int> que;

            MyStack()
            {
            }

            void push(int x)
            {
                que.push(x);
            }

            int pop()
            {
                int size = que.size();
                size--;
                while (size--)
                { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
                    que.push(que.front());
                    que.pop();
                }
                int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
                que.pop();
                return result;
            }

            int top()
            {
                int size = que.size();
                size--;
                while (size--)
                {
                    // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
                    que.push(que.front());
                    que.pop();
                }
                int result = que.front(); // 此时获得的元素就是栈顶的元素了
                que.push(que.front());    // 将获取完的元素也重新添加到队列尾部，保证数据结构没有变化
                que.pop();
                return result;
            }

            bool empty()
            {
                return que.empty();
            }
        };

        20. 有效的括号 class Solution
        {
        public:
            bool isValid(string s)
            {
                if (s.size() % 2 != 0)
                    return false; // 如果s的长度为奇数，一定不符合要求
                stack<char> st;
                for (int i = 0; i < s.size(); i++)
                {
                    if (s[i] == '(')
                        st.push(')');
                    else if (s[i] == '{')
                        st.push('}');
                    else if (s[i] == '[')
                        st.push(']');
                    // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
                    // 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
                    else if (st.empty() || st.top() != s[i])
                        return false;
                    else
                        st.pop(); // st.top() 与 s[i]相等，栈弹出元素
                }
                // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
                return st.empty();
            }
        };

        1047. 删除字符串中的所有相邻重复项

            class Solution
        {
        public:
            string removeDuplicates(string s)
            {
                stack<char> st;
                int n = s.size();
                // 也可以用一个字符串模拟栈，最后直接修改s即可.
                for (int i = 0; i < n; i++)
                {
                    if (!st.empty())
                    {
                        if (s[i] == st.top())
                        {
                            st.pop();
                            continue;
                        }
                    }
                    st.push(s[i]);
                }
                int m = st.size();
                for (int i = m - 1; i >= 0; i--)
                {
                    s[i] = st.top();
                    st.pop();
                }
                s.resize(m);
                return s;
            }
        };

        150. 逆波兰表达式求值 class Solution
        {
        public:
            int evalRPN(vector<string> &tokens)
            {
                stack<long long> st;
                for (int i = 0; i < tokens.size(); i++)
                {
                    if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
                    {
                        long long num1 = st.top();
                        st.pop();
                        long long num2 = st.top();
                        st.pop();
                        if (tokens[i] == "+")
                            st.push(num2 + num1);
                        if (tokens[i] == "-")
                            st.push(num2 - num1);
                        if (tokens[i] == "*")
                            st.push(num2 * num1);
                        if (tokens[i] == "/")
                            st.push(num2 / num1);
                    }
                    else
                    {
                        st.push(stoll(tokens[i]));
                    }
                }
                long long result = st.top();
                return result;
            }
        };

        239. 滑动窗口最大值 class Solution
        {
        public:
            vector<int> maxSlidingWindow(vector<int> &nums, int k)
            {
                int n = nums.size();
                deque<int> q;
                for (int i = 0; i < k; ++i)
                {
                    while (!q.empty() && nums[i] >= nums[q.back()])
                    {
                        q.pop_back();
                    }
                    q.push_back(i);
                }

                vector<int> ans = {nums[q.front()]};
                for (int i = k; i < n; ++i)
                {
                    while (!q.empty() && nums[i] >= nums[q.back()])
                    {
                        q.pop_back();
                    }
                    q.push_back(i);
                    while (q.front() <= i - k)
                    {
                        q.pop_front();
                    }
                    ans.push_back(nums[q.front()]);
                }
                return ans;
            }
        };

        347. 前 K 个高频元素

            class Solution
        {
        public:
            // 1. 自定义比较器：mycomparison
            //    用于让 priority_queue 变成小顶堆。
            class mycomparison
            {
            public:
                // 当我们往堆里 push 元素的时候，这个比较器会决定
                // 哪些元素排在堆顶。这里的 pair<int,int> 的 second 存放的是出现次数(频率)。
                // "return lhs.second > rhs.second;" 表示频率较大的元素优先级更低，
                // 从而堆顶会是"最小的频率"。这就实现了小顶堆的效果。
                bool operator()(const pair<int, int> &lhs, const pair<int, int> &rhs)
                {
                    return lhs.second > rhs.second;
                }
            };

            vector<int> topKFrequent(vector<int> &nums, int k)
            {
                // -------------------------------------------------------------
                // 2. 使用哈希表统计每个数字出现的频率
                //    key   = nums[i] (某个元素)
                //    value = 该元素出现的次数
                // -------------------------------------------------------------
                unordered_map<int, int> freqMap;
                for (int i = 0; i < (int)nums.size(); i++)
                {
                    freqMap[nums[i]]++;
                    // freqMap[nums[i]]++ 表示：以 nums[i] 作为 key，value (出现次数) 自增 1
                }

                // -------------------------------------------------------------
                // 3. 定义一个小顶堆(最小堆)
                //    - 底层容器：vector<pair<int,int>>
                //    - 比较器： mycomparison (将频率小的留在堆顶)
                //
                // priority_queue 默认是最大堆；这里通过传入自定义比较器，改为小顶堆
                // -------------------------------------------------------------
                priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

                // -------------------------------------------------------------
                // 4. 我们想要找前 K 高频的元素，就可以把
                //    <元素, 该元素出现的次数> 压入小顶堆中，但维持堆大小 <= k
                //    这样一来，堆里一直存储的是“目前出现频率最高的 K 个元素”。
                //
                //    具体做法：
                //    - 遍历每个(元素, 频率)对，把它 push 进小顶堆。
                //    - 如果此时堆大小超过 k，就 pop 掉堆顶(意味着弹出“最小”的那个频率)。
                //    => 这样最终堆中存放的就是 K 个“频率最高”的元素
                //       (因为每次超出k就把频率最小的弹掉)。
                // -------------------------------------------------------------
                for (auto it = freqMap.begin(); it != freqMap.end(); it++)
                {
                    // it->first  = 某个元素
                    // it->second = 该元素出现次数
                    pri_que.push(*it);

                    // 如果堆的大小大于 K，说明我们只需要 K 个更大频率的。
                    // 这里是“小顶堆”，堆顶存放最小频率。当 size() > k 时，
                    // pop() 会弹出堆顶(最小的频率)，让堆继续只保留
                    // “频率更大的那 k 个”。
                    if (pri_que.size() > k)
                    {
                        pri_que.pop();
                    }
                }

                // -------------------------------------------------------------
                // 5. 此时优先队列中有 K 个元素，且都对应“前 K 高频”。
                //    但是因为是小顶堆(堆顶是最小频率)，我们要在结果数组中
                //    放入从“最高频率”到“稍低频率”的顺序时，需要把堆里
                //    的元素一个个弹出得到 key。
                //
                //    题目没有要求严格的顺序，只说"可以按任意顺序"返回，
                //    所以只要把堆里这 k 个元素提取出来就行。
                //    这里的写法是倒序往 result 里放，是一种常见写法，
                //    不过题意无要求时，你也可以直接从 i=0 开始放。
                // -------------------------------------------------------------
                vector<int> result(k);
                for (int i = k - 1; i >= 0; i--)
                {
                    // pri_que.top() 拿到“频率最小”的那个 pair，但注意：
                    // 因为我们只留下了 k 个最大的频率，所以这里 pop() 的顺序
                    // 实际拿到的是这 k 个中从小到大的频率，往 result 里倒序存，
                    // 就把频率更高的放在后面位置。
                    //
                    // pair<int,int>.first = 元素值
                    // pair<int,int>.second = 该元素出现次数
                    result[i] = pri_que.top().first;
                    pri_que.pop();
                }

                return result;
            }
        };

        77. 组合
            vector<int>
                temp;
        void dfs(int cur, int n)
        {
            if (cur == n + 1)
            {
                // 记录答案
                // ...
                return;
            }
            // 考虑选择当前位置
            temp.push_back(cur);
            dfs(cur + 1, n, k);
            temp.pop_back();
            // 考虑不选择当前位置
            dfs(cur + 1, n, k);
        }

        .77.组合

            class Solution
        {
        public:
            // 全局(或类成员)变量，用来存储最终结果
            vector<vector<int>> res;
            // 临时路径，用于收集当前组合
            vector<int> path;

            // 回溯函数
            // n: 给定的上限(1..n)
            // k: 需要选出的元素个数
            // index: 当前可以选择数字的起始位置
            void backtracking(int n, int k, int index)
            {
                // 若当前收集到的元素数目 == k，说明得到一个完整组合
                if (path.size() == k)
                {
                    // 将当前组合放入结果中
                    res.push_back(path);
                    return;
                }

                // 在区间 [index..n] 中选择下一个元素
                // 注意：这里是 "i <= n" 不是 "i < n"
                for (int i = index; i <= n; i++)
                {
                    // 1. 选择 i
                    path.push_back(i);
                    // 2. 递归，下一次只能在 (i+1..n) 里选取
                    //    因为组合不允许重复选择，也避免顺序重复
                    backtracking(n, k, i + 1);
                    // 3. 回溯：撤销选择
                    path.pop_back();
                }
            }

            vector<vector<int>> combine(int n, int k)
            {
                // 从数字 1 开始选
                // 因为题意: "范围 [1..n]" => 首个可选数字自然是1
                backtracking(n, k, 1);
                return res;
            }
        };

        216. 组合总和 III class Solution
        {
        public:
            vector<vector<int>> res;
            vector<int> path;
            void backtracking(int k, int n, int sum, int index)
            {
                // 终止条件
                if (path.size() == k)
                {
                    if (sum == n)
                        res.push_back(path);
                    return; //// 如果path.size() == k 但sum != targetSum 直接返回
                }
                for (int i = index; i <= 9; i++)
                {
                    path.push_back(i);
                    sum += i;
                    backtracking(k, n, sum, i + 1);
                    path.pop_back();
                    sum -= i;
                }
            }
            vector<vector<int>> combinationSum3(int k, int n)
            {
                res.clear();  // 可以不加
                path.clear(); // 可以不加
                backtracking(k, n, 0, 1);
                return res;
            }
        };

        131. 分割回文串

            class Solution
        {
        private:
            vector<vector<string>> result;
            vector<string> path; // 放已经回文的子串
            void backtracking(const string &s, int startIndex)
            {
                // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
                if (startIndex >= s.size())
                {
                    result.push_back(path);
                    return;
                }
                for (int i = startIndex; i < s.size(); i++)
                {
                    if (isPalindrome(s, startIndex, i))
                    { // 是回文子串
                        // 获取[startIndex,i]在s中的子串
                        string str = s.substr(startIndex, i - startIndex + 1);
                        path.push_back(str);
                    }
                    else
                    { // 不是回文，跳过
                        continue;
                    }
                    backtracking(s, i + 1); // 寻找i+1为起始位置的子串
                    path.pop_back();        // 回溯过程，弹出本次已经添加的子串
                }
            }
            bool isPalindrome(const string &s, int start, int end)
            {
                for (int i = start, j = end; i < j; i++, j--)
                {
                    if (s[i] != s[j])
                    {
                        return false;
                    }
                }
                return true;
            }

        public:
            vector<vector<string>> partition(string s)
            {
                result.clear();
                path.clear();
                backtracking(s, 0);
                return result;
            }
        };

        93. 复原 IP 地址 class Solution
        {
        private:
            vector<string> res;      // 存储最终合法 IP 地址组合
            vector<string> segments; // 存储当前路径上的 IP 段（如 "255"）

            // 判断子串是否合法
            bool isValid(const string &s, int start, int end)
            {
                if (start > end)
                    return false;

                // 前导零非法（除非该段为0）
                if (s[start] == '0' && start != end)
                    return false;

                int num = 0;
                for (int i = start; i <= end; ++i)
                {
                    if (!isdigit(s[i]))
                        return false;              // 如果不是数字字符，直接非法
                    num = num * 10 + (s[i] - '0'); // 将当前字符累加成整数
                    if (num > 255)
                        return false; // 超出 IP 合法范围，非法
                }

                return true;
            }

            // 回溯函数：startIndex 当前起始字符位置，segmentCount 当前段数
            void backtrack(const string &s, int startIndex, int segmentCount)
            {
                // 如果已经填了4段，并且用完了所有字符，就是合法 IP
                if (segmentCount == 4 && startIndex == s.size())
                {
                    string ip = segments[0];
                    for (int i = 1; i < 4; ++i)
                    {
                        ip += "." + segments[i];
                    }
                    res.push_back(ip);
                    return;
                }

                // 剪枝：段数超过4，或字符已用完但段数不足
                if (segmentCount > 4 || startIndex >= s.size())
                    return;

                // 每段长度最多是3（因为最大255）
                for (int i = startIndex; i < s.size() && i - startIndex < 3; ++i)
                {
                    if (isValid(s, startIndex, i))
                    {
                        string segment = s.substr(startIndex, i - startIndex + 1);
                        segments.push_back(segment);           // 做选择
                        backtrack(s, i + 1, segmentCount + 1); // 递归
                        segments.pop_back();                   // 撤销选择
                    }
                }
            }

        public:
            vector<string> restoreIpAddresses(string s)
            {
                res.clear();
                segments.clear();
                backtrack(s, 0, 0);
                return res;
            }
        };

        78. 子集 class Solution
        {
        private:
            vector<vector<int>> result;
            vector<int> path;
            void backtracking(vector<int> &nums, int startIndex)
            {
                result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
                if (startIndex >= nums.size())
                { // 终止条件可以不加
                    return;
                }
                for (int i = startIndex; i < nums.size(); i++)
                {
                    path.push_back(nums[i]);
                    backtracking(nums, i + 1);
                    path.pop_back();
                }
            }

        public:
            vector<vector<int>> subsets(vector<int> &nums)
            {
                result.clear();
                path.clear();
                backtracking(nums, 0);
                return result;
            }
        };

        90. 子集 II

            class Solution
        {
        private:
            vector<vector<int>> result;
            vector<int> path;
            void backtracking(vector<int> &nums, int startIndex, vector<bool> &used)
            {
                result.push_back(path);
                for (int i = startIndex; i < nums.size(); i++)
                {
                    // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
                    // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
                    // 而我们要对同一树层使用过的元素进行跳过
                    if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)
                    {
                        continue;
                    }
                    path.push_back(nums[i]);
                    used[i] = true;
                    backtracking(nums, i + 1, used);
                    used[i] = false;
                    path.pop_back();
                }
            }

        public:
            vector<vector<int>> subsetsWithDup(vector<int> &nums)
            {
                result.clear();
                path.clear();
                vector<bool> used(nums.size(), false);
                sort(nums.begin(), nums.end()); // 去重需要排序
                backtracking(nums, 0, used);
                return result;
            }
        };

        491. 非递减子序列
            // 版本一
            class Solution
        {
        private:
            vector<vector<int>> result;
            vector<int> path;
            void backtracking(vector<int> &nums, int startIndex)
            {
                if (path.size() > 1)
                {
                    result.push_back(path);
                    // 注意这里不要加return，要取树上的节点
                }
                unordered_set<int> uset; // 使用set对本层元素进行去重
                for (int i = startIndex; i < nums.size(); i++)
                {
                    if ((!path.empty() && nums[i] < path.back()) || uset.find(nums[i]) != uset.end())
                    {
                        continue;
                    }
                    uset.insert(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了
                    path.push_back(nums[i]);
                    backtracking(nums, i + 1);
                    path.pop_back();
                }
            }

        public:
            vector<vector<int>> findSubsequences(vector<int> &nums)
            {
                result.clear();
                path.clear();
                backtracking(nums, 0);
                return result;
            }
        };

        46. 全排列 class Solution
        {
        public:
            vector<vector<int>> result;
            vector<int> path;
            void backtracking(vector<int> &nums, vector<bool> &used)
            {
                // 此时说明找到了一组
                if (path.size() == nums.size())
                {
                    result.push_back(path);
                    return;
                }
                for (int i = 0; i < nums.size(); i++)
                {
                    if (used[i] == true)
                        continue; // path里已经收录的元素，直接跳过
                    used[i] = true;
                    path.push_back(nums[i]);
                    backtracking(nums, used);
                    path.pop_back();
                    used[i] = false;
                }
            }
            vector<vector<int>> permute(vector<int> &nums)
            {
                result.clear();
                path.clear();
                vector<bool> used(nums.size(), false);
                backtracking(nums, used);
                return result;
            }
        };

        47. 全排列 II class Solution
        {
        private:
            vector<vector<int>> result;
            vector<int> path;
            void backtracking(vector<int> &nums, vector<bool> &used)
            {
                // 此时说明找到了一组
                if (path.size() == nums.size())
                {
                    result.push_back(path);
                    return;
                }
                for (int i = 0; i < nums.size(); i++)
                {
                    // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
                    // used[i - 1] == false，说明同一树层nums[i - 1]使用过
                    // 如果同一树层nums[i - 1]使用过则直接跳过
                    if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)
                    {
                        continue;
                    }
                    if (used[i] == false)
                    {
                        used[i] = true;
                        path.push_back(nums[i]);
                        backtracking(nums, used);
                        path.pop_back();
                        used[i] = false;
                    }
                }
            }

        public:
            vector<vector<int>> permuteUnique(vector<int> &nums)
            {
                result.clear();
                path.clear();
                sort(nums.begin(), nums.end()); // 排序
                vector<bool> used(nums.size(), false);
                backtracking(nums, used);
                return result;
            }
        };

        // 时间复杂度: 最差情况所有元素都是唯一的。复杂度和全排列1都是 O(n! * n) 对于 n 个元素一共有 n! 中排列方案。而对于每一个答案，我们需要 O(n) 去复制最终放到 result 数组
        // 空间复杂度: O(n) 回溯树的深度取决于我们有多少个元素

        509. 斐波那契数 class Solution
        {
        public:
            int fib(int N)
            {
                if (N <= 1)
                    return N;
                int dp[2];
                dp[0] = 0;
                dp[1] = 1;
                for (int i = 2; i <= N; i++)
                {
                    int sum = dp[0] + dp[1];
                    dp[0] = dp[1];
                    dp[1] = sum;
                }
                return dp[1];
            }
        };

        332. 重新安排行程 class Solution
        {
        private:
            // 定义航班映射关系数据结构：
            // - 外层unordered_map：键为出发机场，值为一个有序map（按到达机场字典序排列）
            // - 内层map：键为到达机场，值为可用机票数量
            unordered_map<string, map<string, int>> targets;

            // 回溯函数：ticketNum为总机票数，result为当前路径
            bool backtracking(int ticketNum, vector<string> &result)
            {
                // 终止条件：当路径长度 = 机票数+1 时，说明所有机票已用完
                if (result.size() == ticketNum + 1)
                {
                    return true; // 找到有效路径
                }

                // 获取当前所在机场（路径最后一个元素）
                string current = result.back();

                // 遍历当前机场的所有可能到达机场（map保证按字典序遍历）
                // 注意：pair中的key必须为const string，避免修改机场名称破坏map结构
                for (pair<const string, int> &target : targets[current])
                {
                    // 检查当前到达机场是否还有可用机票
                    if (target.second > 0)
                    {
                        // 选择这个机场：加入路径，并消耗一张机票
                        result.push_back(target.first);
                        target.second--;

                        // 递归探索下一层：若找到有效路径，立即返回不再回溯
                        if (backtracking(ticketNum, result))
                            return true;

                        // 回溯：撤销选择，恢复机票数量
                        result.pop_back();
                        target.second++;
                    }
                }
                return false; // 当前路径无解
            }

        public:
            vector<string> findItinerary(vector<vector<string>> &tickets)
            {
                targets.clear(); // 清空旧数据

                // 构建航班映射关系（统计每个出发机场到各到达机场的机票数量）
                for (const vector<string> &vec : tickets)
                {
                    // targets[出发机场][到达机场] 的计数值+1
                    // 如果出发机场不存在，会自动创建并插入新map
                    // 如果到达机场不存在，会自动创建并初始化为0后+1
                    targets[vec[0]][vec[1]]++;
                }

                vector<string> result;
                result.push_back("JFK"); // 起始机场

                // 启动回溯算法（传入总机票数）
                backtracking(tickets.size(), result);

                return result; // 返回字典序最小的有效路径
            }
        };

        51. N 皇后 class Solution
        {
        private:
            vector<vector<string>> res; // 结果棋盘集合

            // 检查当前位置是否有效
            bool isvalid(int row, int col, vector<string> &chessboard, int n)
            {
                // 检查列
                for (int i = 0; i < row; i++)
                { // 这是一个剪枝
                    if (chessboard[i][col] == 'Q')
                    {
                        return false;
                    }
                }
                // 检查 45度角是否有皇后
                for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
                {
                    if (chessboard[i][j] == 'Q')
                    {
                        return false;
                    }
                }
                // 检查 135度角是否有皇后
                for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
                {
                    if (chessboard[i][j] == 'Q')
                    {
                        return false;
                    }
                }
                return true;
            }

            // 回溯法，试图将皇后放置到每一行
            void backtracking(vector<string> &chessboard, int n, int row)
            {
                if (row == n)
                {
                    res.push_back(chessboard);
                    return;
                }

                for (int col = 0; col < n; col++)
                {
                    if (isvalid(row, col, chessboard, n))
                    {
                        chessboard[row][col] = 'Q';           // 放置皇后
                        backtracking(chessboard, n, row + 1); // 递归下一行
                        chessboard[row][col] = '.';           // 回溯，撤销放置
                    }
                }
            }

        public:
            vector<vector<string>> solveNQueens(int n)
            {
                res.clear();
                // 初始化棋盘
                vector<string> chessboard(n, string(n, '.'));
                backtracking(chessboard, n, 0);
                return res;
            }
        };

        37. 解数独 class Solution
        {
        private:
            // 回溯算法函数
            bool backtracking(vector<vector<char>> &board)
            {
                for (int i = 0; i < board.size(); i++)
                { // 遍历行
                    for (int j = 0; j < board[0].size(); j++)
                    { // 遍历列
                        if (board[i][j] == '.')
                        { // 如果当前位置为空（即'.'）
                            for (char k = '1'; k <= '9'; k++)
                            { // 遍历数字1-9，尝试在此位置放置数字k
                                if (isValid(i, j, k, board))
                                {                    // 判断数字k是否可以放置在当前位置
                                    board[i][j] = k; // 放置数字k
                                    if (backtracking(board))
                                        return true;   // 如果找到合适的一组解，立即返回
                                    board[i][j] = '.'; // 回溯，撤销数字k
                                }
                            }
                            return false; // 9个数都试完了，都不行，那么返回false，回溯到上一步
                        }
                    }
                }
                return true; // 遍历完没有返回false，说明已经填满了所有空格，找到解
            }

            // 判断当前位置放置数字val是否符合数独规则
            bool isValid(int row, int col, char val, vector<vector<char>> &board)
            {
                // 判断当前行是否已经有val
                for (int i = 0; i < 9; i++)
                {
                    if (board[row][i] == val)
                    {
                        return false;
                    }
                }

                // 判断当前列是否已经有val
                for (int j = 0; j < 9; j++)
                {
                    if (board[j][col] == val)
                    {
                        return false;
                    }
                }

                // 判断当前3x3子矩阵是否已经有val
                int startRow = (row / 3) * 3;
                int startCol = (col / 3) * 3;
                for (int i = startRow; i < startRow + 3; i++)
                { // 遍历子矩阵的行
                    for (int j = startCol; j < startCol + 3; j++)
                    { // 遍历子矩阵的列
                        if (board[i][j] == val)
                        {
                            return false;
                        }
                    }
                }
                return true; // 如果当前行、列和子矩阵都没有重复的数字，返回true
            }

        public:
            // 主函数，调用回溯算法来解数独
            void solveSudoku(vector<vector<char>> &board)
            {
                backtracking(board); // 调用回溯算法解决数独问题
            }
        };

        劲舞团
#include <bits/stdc++.h>
        using namespace std;

        int main()
        {
            string a, b;
            long long t, pre = -1, k = 0, ans = 0;

            // 读取输入直到结束
            while (cin >> a >> b >> t)
            {
                // 如果两次敲击不相同，重置连击计数
                if (a != b)
                {
                    k = 0, pre = t; // k是连击计数，pre是上一按键的时间戳
                    continue;
                }

                // 如果是第一次符合条件的敲击，开始计算连击
                if (pre == -1)
                {
                    k = 1; // 直接开始计数
                }
                else
                {
                    // 如果当前时间戳与上一时间戳差值小于等于1000，则连击
                    if (t - pre <= 1000)
                    {
                        k++; // 连击次数加1
                    }
                    else
                    {
                        k = 1; // 连击断开，重新开始计数
                    }
                }

                pre = t;           // 更新上一时间戳
                ans = max(ans, k); // 更新最大连击次数
            }

            cout << ans << '\n'; // 输出最大连击次数
            return 0;
        }

        2.艺术与篮球

#include <bits/stdc++.h>
            using namespace std;

        // 存储每个月的天数，索引从 1 到 12，0 索引不使用
        int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

        // 存储每个数字对应的画笔数量
        int cnt[10] = {13, 1, 2, 3, 5, 4, 4, 2, 2, 2};

        // 判断是否为闰年
        bool is_leap(int y)
        {
            // 闰年的规则：能被400整除，或者能被4整除且不能被100整除
            if (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0))
                return true;
            return false;
        }

        // 计算给定日期的数字画笔数是否大于50
        int calc(int y, int m, int d)
        {
            // 将日期转换为字符串，格式为 YYYYMMDD
            string s = to_string(y);
            if (m < 10)
                s += '0'; // 如果月份小于10，加上前导0
            s += to_string(m);
            if (d < 10)
                s += '0'; // 如果日期小于10，加上前导0
            s += to_string(d);

            // 计算数字画笔数
            int res = 0;
            for (auto i : s)
            {
                res += cnt[i - '0']; // 将字符转换为数字，累加对应的画笔数
            }

            // 如果画笔数大于50，返回1，表示符合条件
            return res > 50;
        }

        int main()
        {
            int res = 0; // 记录符合条件的日期数量
            // 遍历 2000 年到 2024 年
            for (int y = 2000; y <= 2024; y++)
            {
                // 2024 年只遍历到 4 月份，其他年份遍历到 12 月
                int up = (y == 2024) ? 4 : 12;

                // 判断当前年份是否是闰年，并调整 2 月的天数
                if (is_leap(y))
                    month[2] = 29; // 闰年，2 月有 29 天
                else
                    month[2] = 28; // 非闰年，2 月有 28 天

                // 遍历每个月
                for (int m = 1; m <= up; m++)
                {
                    // 如果是 2024 年 4 月，最多只遍历到 13 号
                    int up2 = (y == 2024 && m == 4) ? 13 : month[m];

                    // 遍历每一天
                    for (int d = 1; d <= up2; d++)
                    {
                        // 对每一天调用 calc 函数，计算并累加符合条件的日期
                        res += calc(y, m, d);
                    }
                }
            }

            // 输出结果：符合条件的日期数量
            cout << res << '\n';
            return 0;
        }

        2.1买瓜（难）

#include <iostream>
#include <cstring>
#include <algorithm>

            using namespace std;

        typedef long long LL;

        const int N = 35;

        int n, m;     // 瓜个数，希望买到的目标重量
        int w[N];     // 瓜的重量
        int res = 50; // 用于记录劈最少的瓜的个数

        // 深度优先搜索函数，u表示当前选择的瓜，s表示当前选择的总重量，cnt表示当前选择的瓜的数量
        void dfs(int u, LL s, int cnt)
        {
            // 如果当前重量超过目标重量，或者已经选择的瓜的数量超过目标数量，直接返回
            if (s > m || cnt >= m)
                return;
            // 如果 cnt >= m，说明我们已经选择了足够多的劈开瓜，而每次继续选择新的劈开瓜时，
            // 对总重量的贡献将持续减少，因为每次选择的都是半个瓜（w[u] / 2）。
            // 这种减少的方式是递归过程中不断累加小的贡献，最终导致总重量无法增加，甚至降低。

            // 如果当前重量等于目标重量，更新结果，记录最小的瓜的数量
            if (s == m)
            {
                res = cnt;
                return;
            }

            // 如果已经遍历完所有瓜，返回
            if (u == n)
                return;

            // 递归分两种情况：
            // 1. 不选择当前瓜
            dfs(u + 1, s, cnt);
            // 2. 选择当前瓜，分割成两半，重量加上原来的重量的一半
            dfs(u + 1, s + w[u] / 2, cnt + 1);
            // 3. 选择当前瓜，重量加上原来的重量
            dfs(u + 1, s + w[u], cnt);
        }

        int main()
        {
            cin >> n >> m; // 输入瓜的个数和目标重量
            m *= 2;        // 目标重量乘以2，统一使用整数来处理，避免浮点数误差
            for (int i = 0; i < n; ++i)
                cin >> w[i], w[i] *= 2; // 输入每个瓜的重量，并乘以2，转换为整数

            dfs(0, 0, 0); // 从第一个瓜开始，当前重量为0，当前选择的瓜数量为0

            // 如果结果仍然是50，说明没有找到符合条件的解，输出-1
            cout << (res == 50 ? -1 : res) << endl;

            return 0;
        }

        蓝桥杯LITS 游戏
#include <bits/stdc++.h>

            using namespace std;

        int lits[4][4][4][2] = {
            {{{0, 0}, {0, -1}, {-1, -1}, {-2, -1}},
             {{0, 0}, {-1, 0}, {-1, 1}, {-1, 2}},
             {{0, 0}, {-1, 0}, {-2, 0}, {-2, -1}},
             {{0, 0}, {0, -1}, {0, -2}, {-1, 0}}},
            {
                {{0, 0}, {-1, 0}, {-2, 0}, {-3, 0}},
                {{0, 0}, {0, -1}, {0, -2}, {0, -3}},
            },
            {{{0, 0}, {-1, 0}, {-1, -1}, {-1, 1}},
             {{0, 0}, {-1, 0}, {-2, 0}, {-1, -1}},
             {{0, 0}, {0, -1}, {0, -2}, {-1, -1}},
             {{0, 0}, {-1, 0}, {-2, 0}, {-1, 1}}},
            {
                {{0, 0}, {0, -1}, {-1, 0}, {-1, 1}},
                {{0, 0}, {-1, 0}, {-1, -1}, {-2, -1}},
            }};

        int pos[4];
        bool flag, vis[4];

        bool success()
        {
            for (int i = 0; i < 4; i++)
            {
                if (!vis[i])
                    return false;
            }
            return true;
        }

        bool check(int x, int y, int i, int j, vector<vector<int>> &map)
        {
            int N = map.size();
            for (int k = 0; k < 4; k++)
            {
                int dx = x + lits[i][j][k][0];
                int dy = y + lits[i][j][k][1];
                if (dx < 0 || dy < 0 || dx >= N || dy >= N || map[dx][dy] != 1)
                    return false;
            }
            return true;
        }

        void fill(int x, int y, int i, int j, vector<vector<int>> &map, int val)
        {
            for (int k = 0; k < 4; k++)
            {
                int dx = x + lits[i][j][k][0];
                int dy = y + lits[i][j][k][1];
                map[dx][dy] = val;
            }
        }

        void dfs(int x, int y, vector<vector<int>> &map)
        {
            if (flag || x == map.size())
                return;
            if (success())
            {
                flag = true;
                return;
            }
            if (y == map.size())
            {
                dfs(x + 1, 0, map);
                return;
            }
            for (int i = 0; i < 4; i++)
            {
                if (!vis[i] && check(x, y, i, pos[i], map))
                {
                    fill(x, y, i, pos[i], map, 2);
                    vis[i] = true;
                    dfs(x, y + 1, map);
                    vis[i] = false;
                    fill(x, y, i, pos[i], map, 1);
                }
            }
            dfs(x, y + 1, map);
        }

        bool solve(vector<vector<int>> & map)
        {
            flag = false;
            for (int i = 0; i < 4; i++)
            {
                for (int j = 0; j < 2; j++)
                {
                    for (int k = 0; k < 4; k++)
                    {
                        for (int l = 0; l < 2; l++)
                        {
                            memset(vis, false, sizeof(vis));
                            pos[0] = i, pos[1] = j;
                            pos[2] = k, pos[3] = l;
                            dfs(0, 0, map);
                            if (flag)
                                return true;
                        }
                    }
                }
            }
            return false;
        }

        int main()
        {
            int T;
            cin >> T;
            while (T--)
            {
                int N;
                cin >> N;
                vector<vector<int>> map(N, vector<int>(N));
                for (int i = 0; i < N; i++)
                {
                    for (int j = 0; j < N; j++)
                    {
                        cin >> map[i][j];
                    }
                }
                cout << (solve(map) ? "Yes" : "No") << endl;
            }
            return 0;
        }

        3.1 砍柴

#include <bits/stdc++.h>
            using namespace std;
        typedef long long ll;
        const int N = 100000;

        std::vector<int> minp, primes;
        void sieve(int n)
        {
            minp.assign(n + 1, 0);
            primes.clear();

            for (int i = 2; i <= n; i++)
            {
                if (minp[i] == 0)
                {
                    minp[i] = i;
                    primes.push_back(i);
                }

                for (auto p : primes)
                {
                    if (i * p > n)
                    {
                        break;
                    }
                    minp[i * p] = p;
                    if (p == minp[i])
                    {
                        break;
                    }
                }
            }
        }

        int main()
        {
            std::ios::sync_with_stdio(false);
            std::cin.tie(nullptr);

            sieve(N);
            // 是否先手必胜
            vector<int> f(N + 1, 0);

            for (int i = 2; i <= N; ++i)
            {
                for (auto v : primes)
                {
                    if (v > i)
                        break;
                    if (f[i - v] == 0)
                    {
                        f[i] = 1;
                        break;
                    }
                }
            }

            int t;
            cin >> t;
            while (t--)
            {
                int x;
                cin >> x;
                cout << f[x] << '\n';
            }

            return 0;
        }

        蓝桥：蓝桥速算【算法赛】
#include <iostream>
        using namespace std;

        typedef long long LL;

        int main()
        {
            ios::sync_with_stdio(false);
            cin.tie(nullptr);

            int n, q;
            cin >> n >> q;

            LL total = 0;
            for (int i = 0; i < n; ++i)
            {
                int x;
                cin >> x;
                total += x;
            }

            while (q--)
            {
                int l, r;
                cin >> l >> r;
                int len = r - l + 1;

                int even = (len + 1) / 2; // 正项个数（偶下标）
                int odd = len / 2;        // 负项个数（奇下标）

                LL pos = 1LL * even * l + 1LL * even * (even - 1); // 正项和
                LL neg = 1LL * odd * l + 1LL * odd * odd;          // 负项和

                total += pos - neg;
            }

            cout << total << "\n";
            return 0;
        }

        蓝桥：浓缩咖啡
#include <iostream>
#include <vector>
#include <algorithm>
        using namespace std;

        int main()
        {
            int T;
            cin >> T;
            while (T--)
            {
                int N, M;
                cin >> N >> M;
                vector<int> a(N);
                for (int i = 0; i < N; ++i)
                    cin >> a[i];

                int mx = *max_element(a.begin(), a.end());
                int mn = *min_element(a.begin(), a.end());

                if (M >= mn && M <= mx)
                    cout << "YES\n";
                else
                    cout << "NO\n";
            }
            return 0;
        }

        蓝桥：5.破译密码
#include <bits/stdc++.h>

            using namespace std;

        int main()
        {
            int n;
            cin >> n;

            vector<int> t1(n), t2(n);
            for (int i = 0; i < n; ++i)
            {
                cin >> t1[i];
            }
            for (int i = 0; i < n; ++i)
            {
                cin >> t2[i];
            }

            vector<pair<int, int>> gifts(n);
            for (int i = 0; i < n; ++i)
            {
                gifts[i] = {t1[i], t2[i]};
            }

            vector<pair<int, int>> groupA, groupB;
            for (const auto &gift : gifts)
            {
                if (gift.first <= gift.second)
                {
                    groupA.push_back(gift);
                }
                else
                {
                    groupB.push_back(gift);
                }
            }

            sort(groupA.begin(), groupA.end(),
                 [](const pair<int, int> &a, const pair<int, int> &b)
                 {
                     return a.first < b.first;
                 });

            sort(groupB.begin(), groupB.end(),
                 [](const pair<int, int> &a, const pair<int, int> &b)
                 {
                     return a.second > b.second;
                 });

            // 合并组A和组B
            vector<pair<int, int>> sorted_gifts;
            sorted_gifts.insert(sorted_gifts.end(), groupA.begin(), groupA.end());
            sorted_gifts.insert(sorted_gifts.end(), groupB.begin(), groupB.end());

            // 计算总时间
            int sum_t1 = 0;
            for (const auto &gift : sorted_gifts)
            {
                sum_t1 += gift.first;
            }

            int santa_end = 0;
            int current_pack_time = 0;
            for (const auto &gift : sorted_gifts)
            {
                current_pack_time += gift.first;
                int start = max(current_pack_time, santa_end);
                santa_end = start + gift.second;
            }

            int total_time = max(sum_t1, santa_end);
            cout << total_time << endl;

            return 0;
        }

        蓝桥：6.插入数字
#include <bits/stdc++.h>
            using namespace std;

        int main()
        {
            ios::sync_with_stdio(false);
            cin.tie(0), cout.tie(0);

            long long N;
            cin >> N;

            string s = to_string(N);
            set<string> res;

            int len = s.length();

            for (int i = 0; i <= len; i++)
            {
                for (int j = 0; j <= 9; j++)
                {
                    string tmp = s.substr(0, i) + to_string(j) + s.substr(i);
                    if (tmp[0] == '0')
                        continue;
                    res.insert(tmp); // 直接用字符串存
                }
            }

            cout << res.size() << '\n';
            return 0;
        }

        3.1 砍柴（博弈论 + 动态规划）
#include <bits/stdc++.h>
            using namespace std;

        // 用于生成所有小于等于 n 的质数
        vector<int> generatePrimes(int n)
        {
            vector<int> primes;
            for (int i = 2; i <= n; i++)
            {
                bool isPrime = true;
                for (int j = 2; j * j <= i; j++)
                { // 简单试除法
                    if (i % j == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                    primes.push_back(i);
            }
            return primes;
        }

        int main()
        {
            vector<int> primes = generatePrimes(1e5); // 所有 ≤1e5 的质数预处理
            vector<int> dp(1e5 + 1, 0);               // dp[i] = 0 表示必败，1 表示必胜
            dp[0] = dp[1] = 0;                        // 长度为0或1直接输

            // 预处理每个长度的输赢状态（先手能否必胜）
            for (int i = 2; i <= 1e5; i++)
            {
                for (int p : primes)
                {
                    if (p > i)
                        break; // 不能减掉大于当前长度的质数
                    if (dp[i - p] == 0)
                    { // 留给对方的是必败局，自己必赢
                        dp[i] = 1;
                        break;
                    }
                }
            }

            int T;
            cin >> T;
            while (T--)
            {
                int n;
                cin >> n;
                cout << dp[n] << '\n'; // 直接输出结果
            }

            return 0;
        }

        4.1 数字串个数
#include <bits/stdc++.h>         // 包含所有标准库头文件（竞赛编程常用）
            using namespace std; // 使用标准命名空间
        typedef long long ll;    // 定义long long类型别名ll

        const ll mod = 1e9 + 7; // 定义模数为1e9+7

        // 快速幂函数：计算(base^exp) % mod
        ll power(ll base, ll exp, ll mod)
        {
            ll result = 1; // 初始化结果为1
            while (exp > 0)
            { // 当指数大于0时循环
                if (exp % 2 == 1)
                {                                   // 如果当前指数为奇数
                    result = (result * base) % mod; // 乘上当前base
                }
                base = (base * base) % mod; // base平方
                exp /= 2;                   // 指数折半
            }
            return result;
        }

        int main()
        {
            // 步骤1：计算各基数的高次幂模值
            ll a = power(9, 10000, mod); // 9^10000 mod mod → 总可能性（不含0）
            ll b = power(8, 10000, mod); // 8^10000 mod mod → 不含3的情况
            ll c = power(8, 10000, mod); // 8^10000 mod mod → 不含7的情况
            ll d = power(7, 10000, mod); // 7^10000 mod mod → 同时不含3和7的情况

            // 步骤2：应用容斥原理公式
            a = (a - b + mod) % mod; // 减去不含3的情况（+mod防止负数）
            a = (a - c + mod) % mod; // 再减去不含7的情况
            a = (a + d) % mod;       // 补回同时不含3和7的情况

            cout << a << '\n'; // 输出结果
            return 0;
        }

        4.2 召唤数学精灵
#include <bits/stdc++.h>
            using namespace std;

        long long n, cnt, ans;

        // get1(x) = A(x) = 1 + 2 + ... + x = x(x+1)/2
        long long get1(long long x)
        {
            return (x + 1) * x / 2;
        }

        // get2(x) = B(x) = x! (仅在 x <= 9 时可直接计算，避免溢出)
        long long get2(long long x)
        {
            long long res = 1;
            for (int j = 1; j <= x; j++)
            {
                res *= j;
            }
            return res;
        }

        int main()
        {
            // 题目要求的 n
            n = 2024041331404202LL; // 示例写死在代码里

            // 如果 n < 10，直接暴力计算所有 i 的 (A(i) - B(i)) % 100 == 0 ?
            if (n < 10)
            {
                for (int i = 1; i <= n; i++)
                {
                    // (A(i) - B(i)) % 100 == 0 ?
                    // 注意优先级: B(i) % 100, 然后 A(i) - that
                    if ((get1(i) - get2(i)) % 100 == 0)
                    {
                        ans++;
                    }
                }
                cout << ans << '\n';
                return 0;
            }

            // 如果 n >= 10
            // 先处理 i=1..9 的情况(小范围可以直接算)
            for (int i = 1; i <= 9; i++)
            {
                if ((get1(i) - get2(i)) % 100 == 0)
                {
                    ans++;
                }
            }

            // 对于 i >= 10，B(i) = i! 一定含足够多因子2和5，使 B(i) % 100 = 0
            // => (A(i) - B(i)) % 100 = A(i) % 100
            // => A(i) % 100 = 0 <=> i(i+1)/2 % 100 = 0 <=> i(i+1) % 200 = 0

            // 枚举 [0..199]，统计满足 i*(i+1) % 200 == 0 的个数
            for (int i = 0; i < 200; i++)
            {
                // get1(i)*2 = i*(i+1)
                // 如果 i*(i+1) mod 200 == 0 => A(i) mod 100 == 0
                if ((get1(i) * 2) % 200 == 0)
                {
                    cnt++;
                }
            }

            // n/200 块，每块贡献 cnt 个
            ans += (n / 200) * cnt;

            // 还剩下 [1..(n % 200)] 部分再检查
            long long r = n % 200;
            for (int i = 1; i <= r; i++)
            {
                if ((get1(i) * 2) % 200 == 0)
                {
                    ans++;
                }
            }

            cout << ans << '\n';
            return 0;
        }

        2.小球反弹
#include <bits/stdc++.h>
            using namespace std;

        // 用于判断条件是否满足
        bool check(int a, int b)
        {
            // 判断a是否可以被b整除，并且a / b的结果是偶数
            if (a % b == 0 && (a / b) % 2 == 0)
                return true;
            return false;
        }

        int main()
        {
            long long t = 1;            // 初始时间 t 为 1
            int X = 343720, Y = 233333; // 长方形的长和宽

            // 无限循环，直到找到符合条件的t
            while (1)
            {
                int LB = 15 * t; // 水平方向的距离
                int LC = 17 * t; // 垂直方向的距离

                // 检查条件是否满足
                if (check(LB, X) && check(LC, Y))
                {
                    break; // 如果条件满足，跳出循环
                }
                t++; // 否则继续增加 t
            }

            // 计算并输出结果，保留两位小数
            cout << setprecision(2) << fixed << sqrt(15 * t * 15 * t + 17 * t * 17 * t) << '\n';

            return 0;
        }

        3.好数.
#include <iostream>
#include <bits/stdc++.h>
            using namespace std;

        int isgood(long long n)
        {
            int flag = 1; // 标志当前是奇数位还是偶数位
            int res = 1;  // 结果
            while (n)
            {
                long long x = n % 10;
                if ((flag % 2 == 0 && x % 2 != 0) || (flag % 2 != 0 && x % 2 == 0))
                {
                    res = 0;
                    break;
                }
                flag++;
                n /= 10;
            }
            return res;
        }
        int main()
        {
            ios::sync_with_stdio(false);
            cin.tie(0), cout.tie(0);
            long long n;
            cin >> n;
            int sum = 0;
            for (long long i = 1; i <= n; i++)
            {
                if (isgood(i))
                {
                    sum++;
                }
            }
            cout << sum << endl;
            return 0;
        }

        4.R格式

#include <bits/stdc++.h>
            using namespace std;

        string add(string num1, string num2)
        {
            int carry = 0;
            string result;
            int i = num1.length() - 1;
            int j = num2.length() - 1;

            while (i >= 0 || j >= 0 || carry > 0)
            {
                int digit1 = (i >= 0) ? num1[i--] - '0' : 0;
                int digit2 = (j >= 0) ? num2[j--] - '0' : 0;
                int sum = digit1 + digit2 + carry;
                carry = sum / 10;
                result += to_string(sum % 10);
            }

            reverse(result.begin(), result.end());
            return result;
        }

        string multiply(string num1, int num2)
        {
            int carry = 0;
            string result;

            for (int i = num1.length() - 1; i >= 0; --i)
            {
                int digit = num1[i] - '0';
                int product = digit * num2 + carry;
                carry = product / 10;
                result += to_string(product % 10);
            }

            if (carry > 0)
            {
                result += to_string(carry);
            }

            reverse(result.begin(), result.end());
            return result;
        }

        string multiply(string num1, string num2)
        {
            string result = "0";
            for (int i = num2.length() - 1; i >= 0; --i)
            {
                string temp = multiply(num1, num2[i] - '0');
                temp += string(num2.length() - 1 - i, '0');
                result = add(result, temp);
            }
            return result;
        }

        int main()
        {

            int n;
            string d;
            cin >> n >> d;

            size_t pos = d.find('.');
            string d1 = d.substr(0, pos);
            string d2 = d.substr(pos + 1);
            int len_float = d2.size();

            string pow2n = "1";
            for (int i = 1; i <= n; i++)
                pow2n = multiply(pow2n, "2");

            d1 = multiply(d1, pow2n);
            d2 = multiply(d2, pow2n);

            string d2_int = "0";
            if (d2.size() != len_float)
                d2_int = d2.substr(0, d2.size() - len_float);

            int x = d2[d2.size() - len_float] - '0';
            if (x >= 5)
                d2_int = add(d2_int, "1");

            cout << add(d1, d2_int) << '\n';

            return 0;
        }

        5.宝石组合

#include <bits/stdc++.h>
            using namespace std;

        // 全局变量：存储结果以及数字出现频率的数组
        int res, f[100010];

        // 主函数
        int main()
        {
            int n;
            cin >> n; // 输入数字个数

            // 统计每个数字出现的次数
            for (int i = 1; i <= n; i++)
            {
                int x;
                cin >> x;
                f[x]++; // 增加该数字x的出现次数
            }

            // 从最大的g开始，逐步尝试每个g
            for (int g = 100000; g >= 1; g--)
            {
                int cnt = 0;     // 统计符合条件的数字个数
                vector<int> vec; // 用于存储符合条件的数字

                // 通过g的倍数来查找符合条件的数字
                for (int j = g; j <= 100000; j += g)
                {
                    cnt += f[j]; // 将当前倍数j出现的次数加到cnt

                    // 将当前数字j最多加入vec三个数字
                    for (int k = 1; k <= f[j] && vec.size() < 3; k++)
                    {
                        vec.push_back(j); // 将数字j加入vec
                    }

                    // 如果已经找到3个符合条件的数字，提前结束内层循环
                    if (cnt >= 3)
                        break;
                }

                // 如果已经找到了3个符合条件的数字，输出结果
                if (cnt >= 3)
                {
                    for (auto i : vec)
                        cout << i << " "; // 输出这3个数字
                    cout << '\n';         // 换行
                    return 0;             // 找到答案后直接退出程序
                }
            }

            return 0; // 如果没有找到符合条件的三元组，正常退出
        }

        6.数字接龙

#include <bits/stdc++.h>
            using namespace std;

        const int N = 11; // 定义棋盘最大尺寸为11x11
        int n, k;
        int a[N][N], vis[N][N], line[N][N][N][N];                                               // a:棋盘，vis:访问标记，line:表示路径是否交叉
        int nex[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}}; // 8个方向的偏移量

        // 检查坐标是否合法，范围内且未访问
        bool check(int x, int y)
        {
            if (x < 1 || x > n || y < 1 || y > n || vis[x][y])
                return false; // 如果超出边界或已访问返回false
            return true;
        }

        // 深度优先搜索，x, y表示当前坐标，vec记录当前的路径
        void dfs(int x, int y, vector<int> vec)
        {
            // 如果到达右下角且路径已经经过了所有格子，输出路径
            if (x == n && y == n)
            {
                if (vec.size() != n * n - 1)
                    return; // 如果路径长度不符合要求则不合法
                for (auto i : vec)
                    cout << i; // 输出路径
                cout << '\n';
                exit(0); // 找到路径后退出
            }

            // 遍历8个方向
            for (int i = 0; i < 8; i++)
            {
                int tx = x + nex[i][0], ty = y + nex[i][1]; // 计算目标位置

                if (!check(tx, ty))
                    continue; // 检查目标位置是否可访问
                if ((a[x][y] + 1) % k != a[tx][ty])
                    continue; // 检查数字是否递增

                // 检查是否出现交叉路径：如果从(上)走到了(右)，则检查是否与之前的路径重合
                if (i == 1 && (line[x - 1][y][x][y + 1] || line[x][y + 1][x - 1][y]))
                    continue;
                if (i == 5 && (line[x][y - 1][x + 1][y] || line[x + 1][y][x][y - 1]))
                    continue;
                if (i == 3 && (line[x][y + 1][x + 1][y] || line[x + 1][y][x][y + 1]))
                    continue;
                if (i == 7 && (line[x - 1][y][x][y - 1] || line[x][y - 1][x - 1][y]))
                    continue;

                vec.push_back(i); // 添加当前方向到路径

                // 如果当前是对角线方向，记录路径
                if (abs(nex[i][0]) + abs(nex[i][1]) == 2)
                    line[x][y][tx][ty] = 1;
                vis[tx][ty] = 1;  // 标记目标位置为已访问
                dfs(tx, ty, vec); // 继续搜索
                vec.pop_back();   // 回溯，移除最后一个方向
                if (abs(nex[i][0]) + abs(nex[i][1]) == 2)
                    line[x][y][tx][ty] = 0; // 恢复路径
                vis[tx][ty] = 0;            // 恢复目标位置的访问状态
            }
        }

        int main()
        {
            cin >> n >> k; // 输入棋盘大小和数字范围
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    cin >> a[i][j]; // 输入棋盘数字

            vector<int> vec; // 存储路径
            vis[1][1] = 1;   // 标记起始位置已访问
            dfs(1, 1, vec);  // 从起始位置开始搜索

            cout << -1 << '\n'; // 如果找不到路径，则输出 -1
            return 0;
        }

        7.拔河
#include <iostream>
#include <algorithm>
#define int long long
            using namespace std;
        const int N = 1e3 + 10;
        int n, js = 1, a[N], check[N * N];
        signed main()
        {
            cin >> n;
            for (int i = 1; i <= n; i++)
                cin >> a[i];
            for (int i = 1; i <= n; i++)
            { // 我们先通过二层循环，暴力出每一种选法
                int s = 0;
                for (int j = i; j <= n; j++)
                {
                    s += a[j];
                    check[js++] = s;
                }
            } // 可能有谁都不选的选法，check数组从0开始
            sort(check, check + js);
            // 将他们从小到大排序，力量值之和差距最小的一定是相邻的两种选法
            // 不用管区间选择重叠的情况，重叠部分相当于两种选法都没选重叠部分
            int ans = 1e12 + 10;
            for (int i = 1; i < js; i++)
                ans = min(ans, check[i] - check[i - 1]);
            cout << ans;
            return 0;
        }

        第十四届蓝桥杯大赛软件赛省赛C / C++ 大学 B 组

            1.日期统计
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
            using namespace std;

        int main()
        {
            int v[100] = {
                5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7,
                5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9,
                2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3,
                8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6,
                1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3};
            vector<int> dayInmonth = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
            int year = 2023;
            vector<string> res;

            // 生成 2023 年的所有日期字符串
            for (int i = 1; i <= 12; i++)
            {
                for (int j = 1; j <= dayInmonth[i]; j++)
                {
                    string s = to_string(year);
                    // 加月
                    if (i < 10)
                    {
                        s += "0" + to_string(i);
                    }
                    else
                    {
                        s += to_string(i);
                    }
                    // 加日
                    if (j < 10)
                    {
                        s += "0" + to_string(j);
                    }
                    else
                    {
                        s += to_string(j);
                    }
                    res.push_back(s);
                }
            }

            int sum = 0; // 统计个数
            for (const string &date : res)
            {
                int j = 0; // 数组 v 的指针
                for (int i = 0; i < 100 && j < 8; i++)
                {
                    if (to_string(v[i])[0] == date[j])
                    {
                        j++;
                    }
                }
                if (j == 8)
                {
                    sum++;
                }
            }
            cout << sum << '\n';
            return 0;
        }

        2.01串的熵
#include <iostream>
#include <cmath>
            using namespace std;

        const long long n = 23333333;
        const long double target = 11625907.5798;

        long double compute_H(long long c0)
        {
            long long c1 = n - c0;
            long double p0 = (long double)c0 / n;
            long double p1 = (long double)c1 / n;
            return -c0 * p0 * log2(p0) - c1 * p1 * log2(p1);
        }

        int main()
        {
            long long left = 0, right = n / 2;
            long long best_c0 = 0;
            long double min_diff = 1e18;

            // 二分查找优化
            while (left <= right)
            {
                long long mid = left + (right - left) / 2;
                long double H = compute_H(mid);
                long double diff = abs(H - target);

                if (diff < min_diff)
                {
                    min_diff = diff;
                    best_c0 = mid;
                }

                if (H < target)
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }

            cout << best_c0 << endl;
            return 0;
        }

        3.冶炼金属
#include <bits/stdc++.h>
            using namespace std;

        int main()
        {
            ios::sync_with_stdio(false);
            cin.tie(0), cout.tie(0);

            int N;
            cin >> N;
            long long global_min = 1;    // V的最小值初始化为1
            long long global_max = 1e18; // V的最大值初始化为一个大数

            for (int i = 0; i < N; ++i)
            {
                long long A, B;
                cin >> A >> B;

                // 计算当前记录的V的最小值和最大值
                long long min_v = A / (B + 1) + 1;
                long long max_v = A / B;

                // 更新全局范围
                global_min = max(global_min, min_v);
                global_max = min(global_max, max_v);
            }

            cout << global_min << " " << global_max << endl;
            return 0;
        }

        4.飞机降落
#include <iostream>
#include <cstring>
#include <algorithm>

            using namespace std;

        const int N = 15; // 定义飞机的最大数量，这里题目中 n 不超过 10

        // 全局变量
        int n;                // 本测试用例中飞机的数量
        int a[N], b[N], c[N]; // 分别存储每架飞机的到达时刻 (a)、盘旋时间（燃油剩余换算后即 a + D, 存在 b 中）和降落所需时间 (c)
        bool st[N];           // 标记数组，用于表示每架飞机在当前 DFS 排列中是否已经被安排

        /*
         * DFS 函数参数说明：
         * @param u: 当前刚刚安排降落的飞机编号
         * @param last: 当前飞机降落结束后跑道空闲的时间，也就是下一架飞机最早可以开始降落的时间
         * @param cnt: 当前已经安排了多少架飞机降落
         *
         * 函数目的：在以当前飞机 u 为最后降落飞机的前提下，从剩余飞机中寻找一种合法的降落顺序，
         *           使得所有飞机都在各自的时间窗口内开始降落。若存在这样的排列，则返回 true。
         */
        bool dfs(int u, int last, int cnt)
        {
            // 检查当前飞机 u 是否能在当前时间 last 开始降落：
            // b[u] 表示飞机 u 最晚能开始降落的时刻（读取时 b[i] 已经变为 a[i] + D[i]）
            // 如果当前时间 last 已经超过了飞机 u 的截止时刻，则无法安排，返回 false
            if (b[u] < last)
                return false;
            // 比如说 我15盘旋完毕，必须要下降了，但是前面还没降落，
            // 传来的last最早20才可以降落，所以这个选择就不行

            // 如果已经安排了所有 n 架飞机降落，则找到一条合法顺序，返回 true
            if (cnt == n)
                return true;

            // 尝试安排下一架飞机：枚举所有还没有被安排过的飞机
            for (int i = 0; i < n; ++i)
            {
                if (!st[i]) // 如果第 i 架飞机还未被安排
                {
                    st[i] = true; // 标记飞机 i 已经被安排在当前顺序中

                    /*
                     * 计算当前飞机 u 实际降落开始时间：
                     *  - 飞机 u 必须在它的到达时间 a[u] 之后才能降落，
                     *  - 也必须等待跑道空闲时间 last (上一架飞机降落结束时间)
                     * 所以实际开始降落时间为： max(a[u], last)
                     *
                     * 飞机 u 降落结束的时间就是： max(a[u], last) + c[u]
                     *
                     * 因此将飞机 u 降落结束时间作为下一架飞机开始降落的最早时间，
                     * 并将已安排飞机数量 cnt 加 1 后递归调用 dfs 来尝试安排剩下的飞机。
                     */
                    if (dfs(i, max(a[u], last) + c[u], cnt + 1))
                        return true; // 如果递归能成功安排完剩余飞机，则整个安排合法，返回 true

                    st[i] = false; // 回溯：撤销对飞机 i 的安排，尝试其他可能的飞机
                }
            }

            // 如果所有剩余飞机的尝试都不能得到合法的顺序，返回 false
            return false;
        }

        int main()
        {
            int T;
            cin >> T; // 读取测试数据组数

            while (T--)
            {
                // 初始化标记数组 st 为 false
                memset(st, 0, sizeof st);

                // 读取本组测试数据中飞机数量
                cin >> n;
                for (int i = 0; i < n; ++i)
                {
                    // 输入每架飞机的三个参数：到达时刻 a[i]、盘旋时间 D[i]（暂存在 b[i] 中）和降落所需时间 c[i]
                    cin >> a[i] >> b[i] >> c[i];
                    // 将 b[i] 更新为飞机最晚能开始降落的绝对时间：
                    // b[i] = a[i] + D[i]
                    b[i] += a[i];
                }

                // 用 flag 表示是否存在一种合法的降落顺序
                bool flag = false;
                // 由于任意一架飞机都可能成为第一架降落的飞机，
                // 因此我们尝试每一架飞机作为第一个降落的飞机
                for (int i = 0; i < n; ++i)
                {
                    st[i] = true; // 标记飞机 i 作为起始飞机
                    // 调用 DFS，从飞机 i 开始安排，初始跑道空闲时间为 0，已安排飞机数量为 1
                    if (dfs(i, 0, 1))
                    {
                        flag = true; // 如果 DFS 返回 true，则说明存在一种合法顺序
                        break;       // 找到一个合法顺序后退出循环
                    }
                    st[i] = false; // 回溯：撤销飞机 i 的安排，尝试其他可能作为起始飞机的候选
                }

                // 输出结果：如果存在合法顺序则输出 YES，否则输出 NO
                cout << (flag ? "YES" : "NO") << endl;
            }

            return 0;
        }

        5.接龙数列

#include <iostream>
#include <vector>
#include <algorithm>
            using namespace std;

        // 获取数字的首位数字
        int get_head(int x)
        {
            while (x >= 10)
            {
                x /= 10;
            }
            return x;
        }

        int main()
        {
            ios::sync_with_stdio(false);
            cin.tie(0);

            int N;
            cin >> N;
            vector<int> dp(10, 0); // dp[t] 表示以数字t结尾的最长接龙序列长度

            for (int i = 0; i < N; ++i)
            {
                int num;
                cin >> num;
                int t = num % 10;      // 末位数字
                int h = get_head(num); // 首位数字

                // 当前数字可以接在以h结尾的序列后，形成更长的序列
                // 或者作为独立序列（当h未被处理过时，dp[h]初始为0，此时长度为1）
                dp[t] = max(dp[t], dp[h] + 1);
            }

            // 找到所有可能末位中的最长序列长度
            int max_len = *max_element(dp.begin(), dp.end());
            // 最少删除次数 = 原长度 - 最长序列长度
            cout << N - max_len << endl;

            return 0;
        }

        7.子串简写
#include <bits/stdc++.h>
            using namespace std;
        typedef long long LL;
        const int N = 500010;

        int k;
        string s;
        char c1, c2;
        int a[N];
        int main()
        {
            ios_base::sync_with_stdio(false);
            cin.tie(0);
            cout.tie(0);
            cin >> k >> s >> c1 >> c2;
            int n = s.size();
            s = '?' + s;
            for (int i = 1; i <= n; ++i)
            {
                a[i] = (s[i] == c2);
                a[i] += a[i - 1];
            }
            LL ans = 0;
            for (int i = 1; i + k - 2 < n; ++i)
            {
                if (s[i] == c1)
                    ans += a[n] - a[i + k - 2];
            }
            cout << ans << '\n';
            return 0;
        }

        代码随想录 - 动态规划专题：509.斐波那契数

                     class Solution
        {
        public:
            int fib(int N)
            {
                if (N <= 1)
                    return N;
                vector<int> dp(N + 1);
                dp[0] = 0;
                dp[1] = 1;
                for (int i = 2; i <= N; i++)
                {
                    dp[i] = dp[i - 1] + dp[i - 2];
                }
                return dp[N];
            }
        };

        70.爬楼梯 class Solution
        {
        public:
            int climbStairs(int n)
            {
                if (n <= 1)
                    return n;
                vector<int> dp(n + 1);
                dp[1] = 1;
                dp[2] = 2;
                for (int i = 3; i <= n; i++)
                {
                    dp[i] = dp[i - 1] + dp[i - 2];
                }
                return dp[n];
            }
        };

        746. 使用最小花费爬楼梯 class Solution
        {
        public:
            int minCostClimbingStairs(vector<int> &cost)
            {
                vector<int> dp(cost.size() + 1);
                dp[0] = 0;
                dp[1] = 0;
                for (int i = 2; i <= cost.size(); i++)
                {
                    dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
                }
                return dp[cost.size()];
            }
        };

        62.不同路径 class Solution
        {
        public:
            int uniquePaths(int m, int n)
            {
                vector<vector<int>> dp(m, vector<int>(n, 0));
                for (int i = 0; i < m; i++)
                    dp[i][0] = 1;
                for (int j = 0; j < n; j++)
                    dp[0][j] = 1;
                for (int i = 1; i < m; i++)
                {
                    for (int j = 1; j < n; j++)
                    {
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    }
                }
                return dp[m - 1][n - 1];
            }
        };

        63. 不同路径 II

            class Solution
        {
        public:
            int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
            {
                // int n = obstacleGrid.size();
                int m = obstacleGrid.size();
                int n = obstacleGrid[0].size();
                if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) // 这里是==0
                    return 0;
                vector<vector<int>> dp(m, vector<int>(n, 0));

                for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++)
                {
                    dp[i][0] = 1;
                }
                for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++)
                {
                    dp[0][j] = 1;
                }
                for (int i = 1; i < m; i++)
                { // 这里i，j从第二行，列开始。
                    for (int j = 1; j < n; j++)
                    {
                        if (obstacleGrid[i][j] == 1)
                            continue; // 忘记带了
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    }
                }
                return dp[m - 1][n - 1];
            }
        };

        96. 不同的二叉搜索树 class Solution
        {
        public:
            int numTrees(int n)
            {
                vector<int> dp(n + 1);
                dp[0] = 1;
                for (int i = 1; i <= n; i++)
                {
                    for (int j = 1; j <= i; j++)
                    {
                        dp[i] += dp[j - 1] * dp[i - j];
                    }
                }
                return dp[n];
            }
        };

        416. 分割等和子集

            class Solution
        {
        public:
            bool canPartition(vector<int> &nums)
            {
                int sum = 0;

                // dp[i]中的i表示背包内总和
                // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
                // 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
                vector<int> dp(10001, 0);
                for (int i = 0; i < nums.size(); i++)
                {
                    sum += nums[i];
                }
                // 也可以使用库函数一步求和
                // int sum = accumulate(nums.begin(), nums.end(), 0);
                if (sum % 2 == 1)
                    return false;
                int target = sum / 2;

                // 开始 01背包
                for (int i = 0; i < nums.size(); i++)
                {
                    for (int j = target; j >= nums[i]; j--)
                    { // 每一个元素一定是不可重复放入，所以从大到小遍历
                        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
                    }
                }
                // 集合中的元素正好可以凑成总和target
                if (dp[target] == target)
                    return true;
                return false;
            }
        };

        1049.最后一块石头的重量II

            class Solution
        {
        public:
            int lastStoneWeightII(vector<int> &stones)
            {
                vector<int> dp(15001, 0);
                int sum = 0;
                for (int i = 0; i < stones.size(); i++)
                    sum += stones[i];
                int target = sum / 2;
                for (int i = 0; i < stones.size(); i++)
                { // 遍历物品
                    for (int j = target; j >= stones[i]; j--)
                    { // 遍历背包
                        dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
                    }
                }
                return sum - dp[target] - dp[target];
            }
        };

        494. 目标和 class Solution
        {
        public:
            int findTargetSumWays(vector<int> &nums, int target)
            {
                int sum = 0;
                for (int i = 0; i < nums.size(); i++)
                    sum += nums[i];
                if (abs(target) > sum)
                    return 0; // 此时没有方案
                if ((target + sum) % 2 == 1)
                    return 0; // 此时没有方案
                int bagSize = (target + sum) / 2;
                vector<int> dp(bagSize + 1, 0);
                dp[0] = 1;
                for (int i = 0; i < nums.size(); i++)
                {
                    for (int j = bagSize; j >= nums[i]; j--)
                    {
                        dp[j] += dp[j - nums[i]];
                    }
                }
                return dp[bagSize];
            }
        };

        回溯法
        class Solution
        {
        private:
            // 使用 2D vector 进行记忆化，memo[index][current_sum]
            // current_sum 的范围是 0 到 new_target
            // index 的范围是 0 到 nums.size()
            // 这里 current_sum 的偏移量需要注意，如果 sum 可能为负
            // 但在我们的转化问题中，new_target >= 0 且 current_sum >= 0
            // 所以 memo 的第二个维度直接对应 sum 值即可
            vector<vector<int>> memo;
            int target_sum_for_subset; // 存储转换后的目标和 new_target

            // 记忆化搜索的递归函数
            // index: 当前正在考虑 nums 数组中的索引
            // current_sum: 当前已经累加的子集和
            // nums: 输入数组
            // 返回值: 从 nums[index] 开始选择数字，能够使最终子集和达到 target_sum_for_subset 的方法数
            int solve(int index, int current_sum, const vector<int> &nums)
            {
                // 1. 记忆化查找：如果当前状态 (index, current_sum) 的结果已经计算过，直接返回
                if (memo[index][current_sum] != -1)
                {
                    return memo[index][current_sum];
                }

                // 2. 基本情况：如果已经考虑完所有数字
                if (index == nums.size())
                {
                    // 如果当前累加的和等于目标子集和，说明找到了一种方法
                    if (current_sum == target_sum_for_subset)
                    {
                        return 1;
                    }
                    else
                    {
                        // 否则，这种选择组合无法达到目标，方法数为 0
                        return 0;
                    }
                }

                // 3. 递归步骤：对于当前数字 nums[index]，有两种选择

                // 选择 1: 将 nums[index] 加入子集 P (前面加 + 号)
                // 只有当当前和加上 nums[index] 不超过目标子集和时，这种选择才可能最终成功
                int ways_include = 0;
                if (current_sum + nums[index] <= target_sum_for_subset)
                {
                    ways_include = solve(index + 1, current_sum + nums[index], nums);
                }

                // 选择 2: 不将 nums[index] 加入子集 P (意味着它在子集 N 中，前面加 - 号)
                int ways_exclude = solve(index + 1, current_sum, nums);

                // 总方法数 = 选择 nums[index] 的方法数 + 不选择 nums[index] 的方法数
                int total_ways = ways_include + ways_exclude;

                // 4. 记忆化存储：将当前状态的结果存储起来
                memo[index][current_sum] = total_ways;

                // 返回当前状态的总方法数
                return total_ways;
            }

        public:
            // 主函数
            int findTargetSumWays(vector<int> &nums, int target)
            {
                // 计算数组总和
                int total_sum = 0;
                for (int num : nums)
                {
                    total_sum += num;
                }

                // 转化问题的前提条件检查：
                // P = (total_sum + target) / 2 必须是非负整数
                // total_sum + target 必须 >= 0
                // total_sum + target 必须是偶数
                if ((total_sum + target) < 0 || (total_sum + target) % 2 != 0)
                {
                    return 0; // 不满足前提条件，没有方法
                }

                // 转化后的目标子集和
                target_sum_for_subset = (total_sum + target) / 2;

                // 初始化记忆化表格
                // 行数: nums.size() + 1 (考虑到 index 可能达到 nums.size())
                // 列数: target_sum_for_subset + 1 (和的范围从 0 到 target_sum_for_subset)
                // 用 -1 初始化表示未计算
                memo.resize(nums.size() + 1, vector<int>(target_sum_for_subset + 1, -1));

                // 调用记忆化搜索函数开始计算，从索引 0，当前和 0 开始
                return solve(0, 0, nums);
            }
        };

        474. 一和零 class Solution
        {
        public:
            int findMaxForm(vector<string> &strs, int m, int n)
            {
                vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 默认初始化0
                for (string str : strs)
                { // 遍历物品
                    int oneNum = 0, zeroNum = 0;
                    for (char c : str)
                    {
                        if (c == '0')
                            zeroNum++;
                        else
                            oneNum++;
                    }
                    for (int i = m; i >= zeroNum; i--)
                    { // 遍历背包容量且从后向前遍历！
                        for (int j = n; j >= oneNum; j--)
                        {
                            dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                        }
                    }
                }
                return dp[m][n];
            }
        };

        518. 零钱兑换 II

            二维DP

            class Solution
        {
        public:
            int change(int amount, vector<int> &coins)
            {
                int bagSize = amount;

                vector<vector<uint64_t>> dp(coins.size(), vector<uint64_t>(bagSize + 1, 0));

                // 初始化最上行
                for (int j = 0; j <= bagSize; j++)
                {
                    if (j % coins[0] == 0)
                        dp[0][j] = 1;
                }
                // 初始化最左列
                for (int i = 0; i < coins.size(); i++)
                {
                    dp[i][0] = 1;
                }
                // 以下遍历顺序行列可以颠倒
                for (int i = 1; i < coins.size(); i++)
                { // 行，遍历物品
                    for (int j = 0; j <= bagSize; j++)
                    { // 列，遍历背包
                        if (coins[i] > j)
                            dp[i][j] = dp[i - 1][j];
                        else
                            dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
                    }
                }
                return dp[coins.size() - 1][bagSize];
            }
        };

        一维DP
        class Solution
        {
        public:
            int change(int amount, vector<int> &coins)
            {
                vector<uint64_t> dp(amount + 1, 0); // 防止相加数据超int
                dp[0] = 1;                          // 只有一种方式达到0
                for (int i = 0; i < coins.size(); i++)
                { // 遍历物品
                    for (int j = coins[i]; j <= amount; j++)
                    { // 遍历背包
                        dp[j] += dp[j - coins[i]];
                    }
                }
                return dp[amount]; // 返回组合数
            }
        };

        377. 组合总和 Ⅳ class Solution
        {
        public:
            int combinationSum4(vector<int> &nums, int target)
            {
                vector<int> dp(target + 1, 0);
                dp[0] = 1;
                for (int i = 0; i <= target; i++)
                { // 遍历背包
                    for (int j = 0; j < nums.size(); j++)
                    { // 遍历物品
                        if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]])
                        {
                            dp[i] += dp[i - nums[j]];
                        }
                    }
                }
                return dp[target];
            }
        };
        卡码网70.爬楼梯（进阶版）

#include <iostream>
#include <vector>
            using namespace std;
        int main()
        {
            int n, m;
            while (cin >> n >> m)
            {
                vector<int> dp(n + 1, 0);
                dp[0] = 1;
                for (int i = 1; i <= n; i++)
                { // 遍历背包
                    for (int j = 1; j <= m; j++)
                    { // 遍历物品
                        if (i - j >= 0)
                            dp[i] += dp[i - j];
                    }
                }
                cout << dp[n] << endl;
            }
        }

        322. 零钱兑换
            // 版本一
            class Solution
        {
        public:
            int coinChange(vector<int> &coins, int amount)
            {
                vector<int> dp(amount + 1, INT_MAX);
                dp[0] = 0;
                for (int i = 0; i < coins.size(); i++)
                { // 遍历物品
                    for (int j = coins[i]; j <= amount; j++)
                    { // 遍历背包
                        if (dp[j - coins[i]] != INT_MAX)
                        { // 如果dp[j - coins[i]]是初始值则跳过
                            dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                        }
                    }
                }
                if (dp[amount] == INT_MAX)
                    return -1;
                return dp[amount];
            }
        };

        279. 完全平方数
            // 版本一
            class Solution
        {
        public:
            int numSquares(int n)
            {
                vector<int> dp(n + 1, INT_MAX);
                dp[0] = 0;
                for (int i = 0; i <= n; i++)
                { // 遍历背包
                    for (int j = 1; j * j <= i; j++)
                    { // 遍历物品
                        dp[i] = min(dp[i - j * j] + 1, dp[i]);
                    }
                }
                return dp[n];
            }
        };

        -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

                                                  283.移动零 class Solution
        {
        public:
            void moveZeroes(vector<int> &nums)
            {
                int des = -1, cur = 0, n = nums.size();
                while (cur < n)
                {
                    if (nums[cur])
                    {
                        des++;
                        swap(nums[cur], nums[des]);
                    }
                    cur++;
                }
            }
        };

        1089. 复写零
#include <vector>
            using namespace std;

        class Solution
        {
        public:
            void duplicateZeros(vector<int> &arr)
            {
                int cur = 0;        // 当前扫描原数组的下标
                int des = -1;       // 目标写入下标：表示修改后数组中，下一个要写的位置
                int n = arr.size(); // 数组长度

                // 1. 第一次遍历：确定最后一个仍会写入（复写）到结果的原始元素 cur，以及对应的目标下标 des。
                //    对于每个元素：
                //      - 如果是 0，则它在结果中需要写入两次，所以让 des += 2。
                //      - 否则，让 des += 1。
                //    一旦 des ≥ n - 1，说明到达或超过了最后一个可写入的位置，就可以停止。
                while (cur < n)
                {
                    if (arr[cur] == 0)
                    {
                        des += 2;
                    }
                    else
                    {
                        des += 1;
                    }
                    if (des >= n - 1)
                    {
                        break; // 找到最后一个要写入的元素 cur，及其目标位置 des
                    }
                    cur++;
                }

                // 2. 处理边界：如果 des 恰好等于 n，说明最后一个 0 的第二次写入会越界
                //    - 我们只能在末尾写入一次 0 (arr[n-1] = 0)
                //    - 然后将 des 回退两位、cur 自减一，跳过这个零的第二次写入
                if (des == n)
                {
                    arr[n - 1] = 0;
                    des -= 2;
                    cur--;
                }

                // 3. 第二次遍历：从 cur 开始向前，将原数组中的元素写到新位置
                //    这样做可以保证写入时不会覆盖 "还未读取" 的原始值。
                while (cur >= 0)
                {
                    if (arr[cur] != 0)
                    {
                        // 非零元素：仅写入一次
                        arr[des] = arr[cur];
                        des--;
                        cur--;
                    }
                    else
                    {
                        // 零元素：写入两次
                        arr[des] = 0;
                        arr[des - 1] = 0;
                        des -= 2;
                        cur--;
                    }
                }
            }
        };

        202. 快乐数 class Solution
        {
        public:
            int check(int n)
            {
                int sum = 0;
                if (n < 10)
                    return n * n;
                while (n)
                {
                    sum += (n % 10) * (n % 10);
                    n /= 10;
                }
                return sum;
            }
            bool isHappy(int n)
            {
                unordered_map<int, int> mp;
                while (1)
                {
                    n = check(n);

                    if (n == 1)
                    {
                        return true;
                    }
                    if (mp.count(n))
                    {
                        return false;
                    }
                    mp[n] = 1;
                }
            }
        };
        11. 盛最多水的容器 class Solution
        {
        public:
            int maxArea(vector<int> &height)
            {
                int left = 0, right = height.size() - 1, ret = 0;
                while (left < right)
                {
                    int v = min(height[left], height[right]) * (right - left);
                    ret = max(ret, v);
                    // 移动指针
                    if (height[left] < height[right])
                        left++;
                    else
                        right--;
                }
                return ret;
            }
        } 611. 有效三角形的个数 class Solution
        {
        public:
            int triangleNumber(vector<int> &nums)
            {
                int n = nums.size();
                sort(nums.begin(), nums.end());
                int ans = 0;
                for (int i = 0; i < n; ++i)
                {
                    for (int j = i + 1; j < n; ++j)
                    {
                        int left = j + 1, right = n - 1, k = j;
                        while (left <= right)
                        {
                            int mid = (left + right) / 2;
                            if (nums[mid] < nums[i] + nums[j])
                            {
                                k = mid;
                                left = mid + 1;
                            }
                            else
                            {
                                right = mid - 1;
                            }
                        }
                        ans += k - j;
                    }
                }
                return ans;
            }
        };

        LCR 179. 查找总价格为目标值的两个商品  （原：剑指 offer：和为 s 的两个数） class Solution
        {
        public:
            vector<int> twoSum(vector<int> &price, int target)
            {
                vector<int> res;
                int left = 0, right = price.size() - 1;
                while (left < right)
                {
                    if (price[left] + price[right] < target)
                    {
                        left++;
                    }
                    else if (price[left] + price[right] > target)
                    {
                        right--;
                    }
                    else
                    {
                        res.push_back(price[left]);
                        res.push_back(price[right]);
                        return res;
                    }
                }
                return res;
            }
        };

        15. 三数之和
#include <vector>
#include <algorithm>
            using namespace std;

        class Solution
        {
        public:
            vector<vector<int>> threeSum(vector<int> &nums)
            {
                // 1. 对数组进行排序，方便后续双指针和去重操作
                sort(nums.begin(), nums.end());
                vector<vector<int>> res;
                int n = nums.size();

                // 2. 枚举第一个数的索引 i
                //    跳过重复元素，以避免生成重复三元组
                for (int i = 0; i < n - 2;)
                {
                    int left = i + 1;      // 左指针
                    int right = n - 1;     // 右指针
                    int target = -nums[i]; // 我们要找 nums[left] + nums[right] == -nums[i]

                    // 3. 双指针在 (i, n) 范围内寻找两数之和等于 target
                    while (left < right)
                    {
                        int sum = nums[left] + nums[right];
                        if (sum == target)
                        {
                            // 找到一组满足条件的三元组，按值存入结果
                            res.push_back({nums[i], nums[left], nums[right]});

                            // 移动指针，准备寻找下一对
                            ++left;
                            --right;

                            // 4. 去重：跳过与上一次相同的值，避免重复
                            while (left < right && nums[left] == nums[left - 1])
                                ++left;
                            //++left之后，此时的left-1才是原来的，
                            while (left < right && nums[right] == nums[right + 1])
                                --right;
                        }
                        else if (sum < target)
                        {
                            // 和太小，左指针右移以增大 sum
                            ++left;
                        }
                        else
                        {
                            // 和太大，右指针左移以减小 sum
                            --right;
                        }
                    }

                    // 5. 枚举下一个 i，跳过所有与当前 nums[i] 相同的元素
                    ++i;
                    while (i < n - 2 && nums[i] == nums[i - 1])
                        ++i;
                }

                return res;
            }
        };

        18. 四数之和

#include <vector>
#include <algorithm>
            using namespace std;

        class Solution
        {
        public:
            vector<vector<int>> fourSum(vector<int> &nums, int target)
            {
                int n = nums.size();
                vector<vector<int>> res;
                if (n < 4)
                    return res; // 少于 4 个元素，必然无解

                // 1. 对数组进行排序，方便后续双指针和去重操作
                sort(nums.begin(), nums.end());

                // 2. 枚举第一个数的索引 a
                //    跳过重复元素，以避免生成重复四元组
                for (int a = 0; a < n - 3;)
                {
                    // 剩余三个数的目标和
                    long target1 = (long)target - nums[a];

                    // 3. 枚举第二个数的索引 b（在 a 之后）
                    for (int b = a + 1; b < n - 2;)
                    {
                        // 剩余两个数的目标和
                        long target2 = target1 - nums[b];
                        int left = b + 1;  // 左指针
                        int right = n - 1; // 右指针

                        // 4. 双指针在区间 [b+1, n-1] 内寻找两数之和 == target2
                        while (left < right)
                        {
                            long sum2 = (long)nums[left] + nums[right];
                            if (sum2 == target2)
                            {
                                // 找到一组满足条件的四元组
                                res.push_back({nums[a], nums[b], nums[left], nums[right]});

                                // 移动指针，准备寻找下一对
                                ++left;
                                --right;

                                // 5. 去重：跳过与上一次相同的元素
                                while (left < right && nums[left] == nums[left - 1])
                                    ++left;
                                while (left < right && nums[right] == nums[right + 1])
                                    --right;
                            }
                            else if (sum2 < target2)
                            {
                                // 和太小，左指针右移以增大 sum2
                                ++left;
                            }
                            else
                            { // sum2 > target2
                                // 和太大，右指针左移以减小 sum2
                                --right;
                            }
                        }

                        // 6. 枚举下一个 b，跳过重复
                        ++b;
                        while (b < n - 2 && nums[b] == nums[b - 1])
                            ++b;
                    }

                    // 7. 枚举下一个 a，跳过重复
                    ++a;
                    while (a < n - 3 && nums[a] == nums[a - 1])
                        ++a;
                }

                return res;
            }
        };

        209. 长度最小的子数组

            class Solution
        {
        public:
            int minSubArrayLen(int target, vector<int> &nums)
            {
                int n = nums.size();
                int left = 0;      // 窗口左边界
                int sum = 0;       // 窗口元素和
                int ans = INT_MAX; // 记录最小长度，初始化为无穷

                for (int right = 0; right < n; ++right)
                {
                    // 扩张窗口：加入 nums[right]
                    sum += nums[right];

                    // 当窗口内和已经 ≥ target，就尝试收缩左边界
                    while (sum >= target)
                    {
                        // 更新最小长度
                        ans = min(ans, right - left + 1);

                        // 收缩：从 sum 中减去 nums[left]，左边界右移
                        sum -= nums[left];
                        ++left;
                    }
                }

                // 如果 ans 没被更新过，说明没有任何子数组满足要求
                return (ans == INT_MAX ? 0 : ans);
            }
        };

        3. 无重复字符的最长子串.class Solution
        {
        public:
            int lengthOfLongestSubstring(string s)
            {
                int n = s.size();
                int left = 0, len = 0;
                unordered_set<char> st; // O(1) 判断
                for (int right = 0; right < n; ++right)
                {
                    // 如果要加入的字符 s[right] 已经在窗口中
                    while (st.count(s[right]))
                    {
                        // 收缩左边界：抛弃 s[left]
                        st.erase(s[left]);
                        ++left;
                    }
                    // 现在可以无冲突地加入
                    st.insert(s[right]);
                    // 更新最长长度
                    len = max(len, right - left + 1);
                }
                return len;
            }
        };
        1004. 最大连续1的个数 III class Solution
        {
        public:
            int longestOnes(vector<int> &nums, int k)
            {
                int n = nums.size();
                int left = 0, zeros = 0, ans = 0;
                for (int right = 0; right < n; ++right)
                {
                    // 扩张窗口
                    if (nums[right] == 0)
                    {
                        ++zeros;
                    }
                    // 收缩窗口，直到 zeros <= k
                    while (zeros > k)
                    {
                        if (nums[left] == 0)
                        {
                            --zeros;
                        }
                        ++left;
                    }
                    // 此时 [left..right] 窗口内最多有 k 个 0 可以翻
                    ans = max(ans, right - left + 1);
                }
                return ans;
            }
        };

        1658. 将 x 减到 0 的最小操作数

#include <vector>
#include <algorithm>
            using namespace std;

        class Solution
        {
        public:
            int minOperations(vector<int> &nums, int x)
            {
                int sum = 0, n = nums.size();
                for (auto e : nums)
                {
                    sum += e; // 计算数组的总和
                }

                int target = sum - x; // 目标是找到和为 target 的最长子数组
                if (target < 0)
                {
                    return -1; // 如果 target 小于 0，直接返回 -1
                }
                if (target == 0)
                {
                    return n; // 如果 target 等于 0，说明整个数组的和正好等于 x，操作数为 n
                }

                int left = 0;
                int tmp = 0; // 窗口内元素和
                int res = 0; // 最长长度

                for (int right = 0; right < n; ++right)
                {
                    tmp += nums[right]; // 扩大窗口
                    while (tmp > target && left <= right)
                    {
                        tmp -= nums[left]; // 缩小窗口
                        left++;
                    }
                    if (tmp == target)
                    {
                        res = max(res, right - left + 1); // 更新最长长度
                    }
                }

                return res > 0 ? n - res : -1; // 返回结果
            }
        };

        904. 水果成篮
#include <vector>
#include <unordered_map>
#include <algorithm>
            using namespace std;

        class Solution
        {
        public:
            int totalFruit(vector<int> &fruits)
            {
                // 哈希表：键为水果类型，值为当前窗口中该类型水果的数量
                unordered_map<int, int> mp;
                int left = 0; // 滑动窗口左边界
                int res = 0;  // 存放结果：最多可以采摘的水果数

                // 右指针 right 从 0 遍历到 n-1，表示滑动窗口的右边界
                for (int right = 0; right < (int)fruits.size(); ++right)
                {
                    // 1. "进窗口": 将 fruits[right] 对应的水果计入篮子
                    mp[fruits[right]]++;

                    // 2. "出窗口": 如果窗口内的水果种类超过 2 种，就收缩左边界
                    while (mp.size() > 2)
                    {
                        // 将 fruits[left] 对应的那种水果数量减 1
                        if (--mp[fruits[left]] == 0)
                        {
                            // 如果某种水果数量已减到 0，就把该键从哈希表中移除
                            mp.erase(fruits[left]);
                        }
                        // 左边界右移，窗口收缩
                        ++left;
                    }

                    // 3. "更新结果": 当前窗口 [left..right] 肯定只有 <=2 种水果
                    // 窗口大小即为可以采摘的水果数，更新最大值
                    res = max(res, right - left + 1);
                }

                return res;
            }
        };

        438. 找到字符串中所有字母异位词
#include <vector>
#include <string>
#include <unordered_map>
            using namespace std;

        class Solution
        {
        public:
            vector<int> findAnagrams(string s, string p)
            {
                int n1 = s.size(), n2 = p.size();
                // mpp: 目标字符串 p 中每个字符的频次
                unordered_map<char, int> mpp;
                // tmp: 滑动窗口中当前字符的频次
                unordered_map<char, int> tmp;
                vector<int> res;

                // 1. 构造目标频次表 mpp
                for (char ch : p)
                {
                    mpp[ch]++;
                }

                int left = 0;
                // 2. 用滑动窗口遍历 s
                for (int right = 0; right < n1; ++right)
                {
                    // ---- 进窗口 ----
                    // 将 s[right] 添加到窗口频次表 tmp
                    tmp[s[right]]++;

                    // ---- 出窗口 ----
                    // 当窗口长度超过 n2 时，需要收缩左边界
                    while (right - left + 1 > n2)
                    {
                        // 将 s[left] 从窗口中移除：频次减 1
                        tmp[s[left]]--;
                        // 如果某字符频次变为 0，则从 tmp 中删除该键
                        if (tmp[s[left]] == 0)
                        {
                            tmp.erase(s[left]);
                        }
                        // 左边界右移，窗口收缩
                        ++left;
                    }

                    // ---- 更新结果 ----
                    // 当窗口大小正好等于 n2 且频次表相同时，说明找到一个异位词
                    if (tmp == mpp)
                    {
                        res.push_back(left);
                    }
                }
                return res;
            }
        };

        30. 串联所有单词的子串

#include <vector>
#include <string>
#include <unordered_map>
            using namespace std;

        class Solution
        {
        public:
            vector<int> findSubstring(const string &s, const vector<string> &words)
            {
                int n = s.size(), k = words.size();
                if (k == 0)
                    return {};
                int L = words[0].size();
                int total = k * L;
                if (n < total)
                    return {};

                // 1. 先统计目标单词频次
                unordered_map<string, int> need;
                for (auto &w : words)
                {
                    need[w]++;
                }

                vector<int> res;
                // 2. 按单词长度 L，把 s 分为 L 条“链”，每条链起点为 offset
                for (int offset = 0; offset < L; ++offset)
                {
                    int left = offset, count = 0;
                    unordered_map<string, int> window;
                    // 这条链上的每一步都是向右跨 L
                    for (int right = offset; right + L <= n; right += L)
                    {
                        // 2.1 “进窗口”：取 [right, right+L)
                        string w = s.substr(right, L);
                        // 如果这不是一个合法单词，就直接清空窗口，left 跳到下一个位置
                        if (!need.count(w))
                        {
                            window.clear();
                            count = 0;
                            left = right + L;
                            continue;
                        }
                        // 否则加入 window 计数
                        window[w]++;
                        count++;
                        // 2.2 “收窗口”：若某个单词超了 need 的频次，就不断把 left 端的窗口收缩一个单词
                        while (window[w] > need[w])
                        {
                            string leftWord = s.substr(left, L);
                            window[leftWord]--;
                            count--;
                            left += L;
                        }
                        // 2.3 “更新结果”：当窗口里正好收了 k 个单词，就找到一个起点
                        if (count == k)
                        {
                            res.push_back(left);
                            // 然后再往前删一个单词，为了找下一个起点
                            string leftWord = s.substr(left, L);
                            window[leftWord]--;
                            count--;
                            left += L;
                        }
                    }
                }
                return res;
            }
        };

        76. 最小覆盖子串 class Solution
        {
        public:
            string minWindow(string s, string t)
            {
                int hash1[128] = {0}; // 统计字符串 t 中每⼀个字符的频次
                int kinds = 0;        // 统计有效字符有多少种
                for (auto ch : t)
                    if (hash1[ch]++ == 0)
                        kinds++;
                int hash2[128] = {0}; // 统计窗⼝内每个字符的频次
                int minlen = INT_MAX, begin = -1;
                for (int left = 0, right = 0, count = 0; right < s.size(); right++)
                {
                    char in = s[right];
                    if (++hash2[in] == hash1[in])
                        count++;           // 进窗⼝ + 维护 count
                    while (count == kinds) // 判断条件
                    {
                        if (right - left + 1 < minlen) // 更新结果
                        {
                            minlen = right - left + 1;
                            begin = left;
                        }
                        char out = s[left++];
                        if (hash2[out]-- == hash1[out])
                            count--; // 出窗⼝ + 维护 count
                    }
                }
                if (begin == -1)
                    return "";
                else
                    return s.substr(begin, minlen);
            }
        };

        97. 交错字符串 class Solution
        {
        public:
            bool isInterleave(string s1, string s2, string s3)
            {
                auto f = vector<vector<int>>(s1.size() + 1, vector<int>(s2.size() + 1, false));

                int n = s1.size(), m = s2.size(), t = s3.size();

                if (n + m != t)
                {
                    return false;
                }

                f[0][0] = true;
                for (int i = 0; i <= n; ++i)
                {
                    for (int j = 0; j <= m; ++j)
                    {
                        int p = i + j - 1;
                        if (i > 0)
                        {
                            f[i][j] |= (f[i - 1][j] && s1[i - 1] == s3[p]);
                        }
                        if (j > 0)
                        {
                            f[i][j] |= (f[i][j - 1] && s2[j - 1] == s3[p]);
                        }
                    }
                }

                return f[n][m];
            }
        };
        LCR 173. 点名 class Solution
        {
        public:
            int takeAttendance(vector<int> &records)
            {
                int i = 0, j = records.size() - 1;
                while (i <= j)
                {
                    int m = (i + j) / 2;
                    if (records[m] == m)
                        i = m + 1;
                    else
                        j = m - 1;
                }
                return i;
            }
        };

        // 153. 寻找旋转排序数组中的最小值
        class Solution
        {
        public:
            int findMin(vector<int> &nums)
            {
                int low = 0;
                int high = nums.size() - 1;
                while (low < high)
                {
                    int pivot = low + (high - low) / 2;
                    if (nums[pivot] < nums[high])
                    {
                        high = pivot;
                    }
                    else
                    {
                        low = pivot + 1;
                    }
                }
                return nums[low];
            }
        };
        // 34. 在排序数组中查找元素的第一个和最后一个位置
        class Solution
        {
        public:
            int binarySearch(vector<int> &nums, int target, bool lower)
            {
                int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
                while (left <= right)
                {
                    int mid = (left + right) / 2;
                    if (nums[mid] > target || (lower && nums[mid] >= target))
                    {
                        right = mid - 1;
                        ans = mid;
                    }
                    else
                    {
                        left = mid + 1;
                    }
                }
                return ans;
            }

            vector<int> searchRange(vector<int> &nums, int target)
            {
                int leftIdx = binarySearch(nums, target, true);
                int rightIdx = binarySearch(nums, target, false) - 1;
                if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target)
                {
                    return vector<int>{leftIdx, rightIdx};
                }
                return vector<int>{-1, -1};
            }
        };
        // 35. 搜索插入位置
        class Solution
        {
        public:
            int searchInsert(vector<int> &nums, int target)
            {
                int n = nums.size();
                int left = 0, right = n - 1, ans = n;
                while (left <= right)
                {
                    int mid = ((right - left) >> 1) + left;
                    if (target <= nums[mid])
                    {
                        ans = mid;
                        right = mid - 1;
                    }
                    else
                    {
                        left = mid + 1;
                    }
                }
                return ans;
            }
        };
        // 69. x 的平方根
        class Solution
        {
        public:
            int mySqrt(int x)
            {
                int l = 0, r = x, ans = -1;
                while (l <= r)
                {
                    int mid = l + (r - l) / 2;
                    if ((long long)mid * mid <= x)
                    {
                        ans = mid;
                        l = mid + 1;
                    }
                    else
                    {
                        r = mid - 1;
                    }
                }
                return ans;
            }
        };
        // 852. 山脉数组的峰顶索引
        class Solution
        {
        public:
            int peakIndexInMountainArray(vector<int> &arr)
            {
                int n = arr.size();
                int ans = -1;
                for (int i = 1; i < n - 1; ++i)
                {
                    if (arr[i] > arr[i + 1])
                    {
                        ans = i;
                        break;
                    }
                }
                return ans;
            }
        };
        // 162. 寻找峰值
        class Solution
        {
        public:
            int findPeakElement(vector<int> &nums)
            {
                return max_element(nums.begin(), nums.end()) - nums.begin();
            }
        };

        // 153. 寻找旋转排序数组中的最小值
        class Solution
        {
        public:
            int findMin(vector<int> &nums)
            {
                int low = 0;
                int high = nums.size() - 1;
                while (low < high)
                {
                    int pivot = low + (high - low) / 2;
                    if (nums[pivot] < nums[high])
                    {
                        high = pivot;
                    }
                    else
                    {
                        low = pivot + 1;
                    }
                }
                return nums[low];
            }
        };

        // 前缀和算法： DP34 【模板】一维前缀和
#include <iostream>
        using namespace std;
        const int N = 100010;
        long long arr[N], dp[N];
        int n, q;
        int main()
        {
            cin >> n >> q;
            // 读取数据
            for (int i = 1; i <= n; i++)
                cin >> arr[i];
            // 处理前缀和数组
            for (int i = 1; i <= n; i++)
                dp[i] = dp[i - 1] + arr[i];
            while (q--)
            {
                int l, r;
                cin >> l >> r;
                // 计算区间和
                cout << dp[r] - dp[l - 1] << endl;
            }
            return 0;
        }
        // DP35 【模板】二维前缀和
#include <iostream>
        using namespace std;
        const int N = 1010;
        int arr[N][N];
        long long dp[N][N];
        int n, m, q;
        int main()
        {
            cin >> n >> m >> q;
            // 读入数据
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                    cin >> arr[i][j];
            // 处理前缀和矩阵
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
            // 使用前缀和矩阵
            int x1, y1, x2, y2;
            while (q--)
            {
                cin >> x1 >> y1 >> x2 >> y2;
                cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
            }
        }
        // 724. 寻找数组的中心下标
        class Solution
        {
        public:
            int pivotIndex(vector<int> &nums)
            {
                // lsum[i] 表示：[0, i - 1] 区间所有元素的和
                // rsum[i] 表示：[i + 1, n - 1] 区间所有元素的和
                int n = nums.size();
                vector<int> lsum(n), rsum(n);
                // 预处理前缀和后缀和数组
                for (int i = 1; i < n; i++)
                    lsum[i] = lsum[i - 1] + nums[i - 1];
                for (int i = n - 2; i >= 0; i--)
                    rsum[i] = rsum[i + 1] + nums[i + 1];
                // 判断
                for (int i = 0; i < n; i++)
                    if (lsum[i] == rsum[i])
                        return i;
                return -1;
            }
        };
        // 238. 除自身以外数组的乘积
        class Solution
        {
        public:
            vector<int> productExceptSelf(
                vector<int> &nums)
            { // lprod 表示：[0, i - 1] 区间内所有元素的乘积
                // rprod 表示：[i + 1, n - 1] 区间内所有元素的乘积
                int n = nums.size();
                vector<int> lprod(n + 1), rprod(n + 1);
                lprod[0] = 1, rprod[n - 1] = 1;
                // 预处理前缀积以及后缀积
                for (int i = 1; i < n; i++)
                    lprod[i] = lprod[i - 1] * nums[i - 1];
                for (int i = n - 2; i >= 0; i--)
                    rprod[i] = rprod[i + 1] * nums[i + 1];
                // 处理结果数组
                vector<int> ret(n);
                for (int i = 0; i < n; i++)
                    ret[i] = lprod[i] * rprod[i];
                return ret;
            }
        };
        // 560. 和为 K 的子数组
        class Solution
        {
        public:
            int subarraySum(vector<int> &nums, int k)
            {
                int count = 0;
                for (int start = 0; start < nums.size(); ++start)
                {
                    int sum = 0;
                    for (int end = start; end >= 0; --end)
                    {
                        sum += nums[end];
                        if (sum == k)
                        {
                            count++;
                        }
                    }
                }
                return count;
            }

            // 974. 和可被 K 整除的子数组
            class Solution
            {
            public:
                int subarraysDivByK(vector<int> &nums, int k)
                {
                    unordered_map<int, int> hash;
                    // 哈希表：key 表示前缀和对 k 取模后的余数，value 表示这种余数出现的次数

                    hash[0 % k] = 1;
                    // 初始化：前缀和为 0 时余数为 0，它本身也可以作为有效子数组（例如 nums = [5], k = 5）

                    int sum = 0; // 前缀和
                    int ret = 0; // 满足条件的子数组个数

                    for (auto x : nums)
                    {
                        sum += x; // 更新当前的前缀和

                        // 计算当前前缀和的余数（注意：防止出现负数余数）
                        // C++中负数取模可能为负，因此用 (sum % k + k) % k 规范化为非负
                        int r = (sum % k + k) % k;

                        // 如果这个余数 r 在之前出现过，说明存在某段子数组和能被 k 整除
                        // 根据同余定理：前缀和对 k 取模相同，表示它们之间的差是 k 的倍数
                        if (hash.count(r))
                        {
                            ret += hash[r]; // 加上所有之前出现过这个余数的次数
                        }

                        // 更新当前余数的出现次数
                        hash[r]++;
                    }

                    return ret; // 返回符合条件的子数组个数
                }
            };
            // 525. 连续数组
            class Solution
            {
            public:
                int findMaxLength(vector<int> &nums)
                {
                    int maxLength = 0;
                    unordered_map<int, int> mp;
                    int counter = 0;
                    mp[counter] = -1;
                    int n = nums.size();
                    for (int i = 0; i < n; i++)
                    {
                        int num = nums[i];
                        if (num == 1)
                        {
                            counter++;
                        }
                        else
                        {
                            counter--;
                        }
                        if (mp.count(counter))
                        {
                            int prevIndex = mp[counter];
                            maxLength = max(maxLength, i - prevIndex);
                        }
                        else
                        {
                            mp[counter] = i;
                        }
                    }
                    return maxLength;
                }
            };

            // 1314. 矩阵区域和
            class Solution
            {
            public:
                int get(const vector<vector<int>> &pre, int m, int n, int x, int y)
                {
                    x = max(min(x, m), 0);
                    y = max(min(y, n), 0);
                    return pre[x][y];
                }

                vector<vector<int>> matrixBlockSum(vector<vector<int>> &mat, int K)
                {
                    int m = mat.size(), n = mat[0].size();
                    vector<vector<int>> P(m + 1, vector<int>(n + 1));
                    for (int i = 1; i <= m; ++i)
                    {
                        for (int j = 1; j <= n; ++j)
                        {
                            P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1];
                        }
                    }

                    vector<vector<int>> ans(m, vector<int>(n));
                    for (int i = 0; i < m; ++i)
                    {
                        for (int j = 0; j < n; ++j)
                        {
                            ans[i][j] = get(P, m, n, i + K + 1, j + K + 1) - get(P, m, n, i - K, j + K + 1) - get(P, m, n, i + K + 1, j - K) + get(P, m, n, i - K, j - K);
                        }
                    }
                    return ans;
                }
            };
            // 268. 丢失的数字
            class Solution
            {
            public:
                int missingNumber(vector<int> &nums)
                {
                    unordered_set<int> set;
                    int n = nums.size();
                    for (int i = 0; i < n; i++)
                    {
                        set.insert(nums[i]);
                    }
                    int missing = -1;
                    for (int i = 0; i <= n; i++)
                    {
                        if (!set.count(i))
                        {
                            missing = i;
                            break;
                        }
                    }
                    return missing;
                }
            };
            // 371. 两整数之和
            class Solution
            {
            public:
                int getSum(int a, int b)
                {
                    while (b != 0)
                    {
                        int x = a ^ b;                                   // 先算出无进位相加的结果
                        unsigned int carry = (unsigned int)(a & b) << 1; // 算出进位
                        a = x;
                        b = carry;
                    }
                    return a;
                }
            };
            // 137. 只出现一次的数字 II
            class Solution
            {
            public:
                int singleNumber(vector<int> &nums)
                {
                    int ret = 0;
                    for (int i = 0; i < 32; i++) // 依次去修改 ret 中的每一位
                    {
                        int sum = 0;
                        for (int x : nums) // 计算nums中所有的数的第 i 位的和
                            if (((x >> i) & 1) == 1)
                                sum++;
                        sum %= 3;
                        if (sum == 1)
                            ret |= 1 << i;
                    }
                    return ret;
                }
            };
            // 面试题 17.19. 消失的两个数字
            class Solution
            {
            public:
                vector<int> missingTwo(vector<int> &nums)
                {
                    int xorsum = 0;
                    int n = nums.size() + 2;
                    for (int num : nums)
                    {
                        xorsum ^= num;
                    }
                    for (int i = 1; i <= n; i++)
                    {
                        xorsum ^= i;
                    }
                    // 防止溢出
                    int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));
                    int type1 = 0, type2 = 0;
                    for (int num : nums)
                    {
                        if (num & lsb)
                        {
                            type1 ^= num;
                        }
                        else
                        {
                            type2 ^= num;
                        }
                    }
                    for (int i = 1; i <= n; i++)
                    {
                        if (i & lsb)
                        {
                            type1 ^= i;
                        }
                        else
                        {
                            type2 ^= i;
                        }
                    }
                    return {type1, type2};
                }
            };
            // 191. 位1的个数
            class Solution
            {
            public:
                int hammingWeight(int n)
                {
                    int sum = 0;
                    for (int i = 0; i < 32; i++)
                    {
                        if (n & (1 << i))
                        {
                            sum++;
                        }
                    }
                    return sum;
                }
            };
            // 461. 汉明距离
            class Solution
            {
            public:
                int hammingDistance(int x, int y)
                {
                    int s = x ^ y, ret = 0;
                    while (s)
                    {
                        ret += s & 1;
                        s >>= 1;
                    }
                    return ret;
                }
            };
// BC153 [NOIP2010]数字统计
#include <iostream>
            using namespace std;

            int main()
            {
                int l, r;
                cin >> l >> r;
                int res = 0;
                for (int i = l; i <= r; i++)
                {

                    int temp = i;
                    while (temp)
                    {
                        if (temp % 10 == 2)
                            res++;
                        temp /= 10;
                    }
                }
                cout << res << endl;
                return 0;
            }
            // 64 位输出请用 printf("%lld")

            // 2220. 转换数字的最少位翻转次数(同 461)
            class Solution
            {
            public:
                int minBitFlips(int start, int goal)
                {
                    // 1010
                    // 0111 有三位不同

                    // 011
                    // 100 //有三位不同
                    int res = 0;
                    int y = start ^ goal;
                    while (y)
                    {
                        y &= (y - 1);
                        res++;
                    }
                    return res;
                }
            };
            // 338. 比特位计数
            class Solution
            {
            public:
                int count(int n)
                {
                    int temp = 0;
                    while (n)
                    {
                        n &= (n - 1);
                        temp++;
                    }
                    return temp;
                }
                vector<int> countBits(int n)
                {
                    vector<int> res;
                    for (int i = 0; i <= n; i++)
                    {
                        res.push_back(count(i));
                    }
                    return res;
                }
            };
            // 136. 只出现一次的数字
            class Solution
            {
            public:
                int singleNumber(vector<int> &nums)
                {
                    int temp = 0;
                    for (auto e : nums)
                    {
                        temp ^= e;
                    }
                    return temp;
                }
            };
            // 260. 只出现一次的数字 III
            class Solution
            {
            public:
                vector<int> singleNumber(vector<int> &nums)
                {
                    int temp = 0;
                    for (auto e : nums)
                    {
                        temp ^= e; // 对所有数字进行异或，得到 x1 ^ x2
                    }

                    // 特殊情况处理，如果 temp 是 INT_MIN，避免溢出
                    int r = (temp == INT_MIN) ? INT_MIN : (temp & (-temp)); // 获取最低有效位

                    int type1 = 0, type2 = 0;
                    for (auto e : nums)
                    {
                        if (e & r)
                        { // 通过最低有效位将数字分成两类
                            type1 ^= e;
                        }
                        else
                        {
                            type2 ^= e;
                        }
                    }

                    return {type1, type2}; // 返回这两个只出现一次的数字
                }
            };
            // 215. 数组中的第K个最大元素
            class Solution
            {
            public:
                int findKthLargest(vector<int> &nums, int k)
                {
                    return quickSelect(nums, k);
                }

            private:
                int quickSelect(vector<int> &nums, int k)
                {
                    // 随机选择基准数
                    int pivot = nums[rand() % nums.size()];
                    // 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中
                    vector<int> big, equal, small;
                    for (int num : nums)
                    {
                        if (num > pivot)
                            big.push_back(num);
                        else if (num < pivot)
                            small.push_back(num);
                        else
                            equal.push_back(num);
                    }
                    // 第 k 大元素在 big 中，递归划分
                    if (k <= big.size())
                        return quickSelect(big, k);
                    // 第 k 大元素在 small 中，递归划分
                    if (nums.size() - small.size() < k)
                        return quickSelect(small, k - nums.size() + small.size());
                    // 第 k 大元素在 equal 中，直接返回 pivot
                    return pivot;
                }
            };

            // 面试题 02.07. 链表相交
            /**
             * Definition for singly-linked list.
             * struct ListNode {
             *     int val;
             *     ListNode *next;
             *     ListNode(int x) : val(x), next(NULL) {}
             * };
             */
            class Solution
            {
            public:
                ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
                {
                    unordered_set<ListNode *> visited;
                    ListNode *temp = headA;
                    while (temp != nullptr)
                    {
                        visited.insert(temp);
                        temp = temp->next;
                    }
                    temp = headB;
                    while (temp != nullptr)
                    {
                        if (visited.count(temp))
                        {
                            return temp;
                        }
                        temp = temp->next;
                    }
                    return nullptr;
                }
            };
            // 234. 回文链表
            /**
             * Definition for singly-linked list.
             * struct ListNode {
             *     int val;
             *     ListNode *next;
             *     ListNode() : val(0), next(nullptr) {}
             *     ListNode(int x) : val(x), next(nullptr) {}
             *     ListNode(int x, ListNode *next) : val(x), next(next) {}
             * };
             */
            class Solution
            {
            public:
                ListNode *reverse(ListNode *head)
                {
                    ListNode *prev = nullptr;
                    ListNode *curr = head;
                    while (curr != nullptr)
                    {
                        // 1->2->3
                        // 1<-2<-3  3是头结点
                        ListNode *next_temp = curr->next;
                        curr->next = prev;
                        prev = curr;
                        curr = next_temp;
                    }
                    return prev;
                }
                bool isPalindrome(ListNode *head)
                {
                    if (!head || !head->next)
                        return true;
                    ListNode *slow = head, *fast = head;
                    ListNode *first_half_end = head;
                    while (fast != nullptr && fast->next != nullptr)
                    {
                        first_half_end = slow; // 关键
                        slow = slow->next;
                        fast = fast->next->next;
                    }

                    first_half_end->next = nullptr;
                    ListNode *second_half_head = reverse(slow);

                    ListNode *p1 = head;
                    ListNode *p2 = second_half_head;
                    bool is_palindrome = true; // 默认假设链表是回文的
                    while (p1 != nullptr && p2 != nullptr)
                    {
                        if (p1->val != p2->val)
                        {
                            is_palindrome = false;
                            break;
                        }
                        p1 = p1->next;
                        p2 = p2->next;
                    }
                    ListNode *original_second_half_head = reverse(second_half_head);
                    first_half_end->next = original_second_half_head;
                    return is_palindrome;
                }
            };
            // 面试题 02.04. 分割链表
            /**
             * Definition for singly-linked list.
             * struct ListNode {
             *     int val;
             *     ListNode *next;
             *     ListNode() : val(0), next(nullptr) {}
             *     ListNode(int x) : val(x), next(nullptr) {}
             *     ListNode(int x, ListNode *next) : val(x), next(next) {}
             * };
             */
            class Solution
            {
            public:
                ListNode *partition(ListNode *head, int x)
                {
                    ListNode *minhead = new ListNode(-1); // 虚拟头结点
                    ListNode *maxhead = new ListNode(-1);
                    ListNode *curmin = minhead;
                    ListNode *curmax = maxhead;
                    ListNode *cur = head;
                    while (cur)
                    {
                        ListNode *next_temp = cur->next;
                        if (cur->val >= x)
                        {
                            curmax->next = cur;
                            curmax = curmax->next;
                        }
                        else
                        {
                            curmin->next = cur;
                            curmin = curmin->next;
                        }
                        cur->next = nullptr;
                        cur = next_temp;
                    }
                    curmax->next = nullptr;
                    curmin->next = maxhead->next;

                    return minhead->next;
                }
            };
            // 1576. 替换所有的问号
            // 函数用于将字符串中的 '?' 替换为小写字母，使最终字符串不包含连续重复字符
            string modifyString(string s)
            {
                int n = s.length(); // 获取字符串的长度

                // 遍历字符串中的每一个字符
                for (int i = 0; i < n; ++i)
                {
                    // 如果当前字符是 '?'
                    if (s[i] == '?')
                    {
                        // 尝试用 'a', 'b', 'c' 等小写字母来替换它
                        // 题目保证答案总是存在的，所以我们只需要尝试几个字符就能找到合适的
                        for (char ch = 'a'; ch <= 'c'; ++ch)
                        { // 尝试 'a', 'b', 'c'
                            // 检查当前尝试的字符 ch 是否与左边的字符冲突
                            // 如果 i > 0 且 s[i-1] 存在且等于 ch，则冲突
                            bool conflict_left = (i > 0 && s[i - 1] == ch);

                            // 检查当前尝试的字符 ch 是否与右边的字符冲突
                            // 如果 i < n-1 且 s[i+1] 存在且等于 ch，则冲突
                            bool conflict_right = (i < n - 1 && s[i + 1] == ch);

                            // 如果 ch 不与左边和右边的字符冲突
                            if (!conflict_left && !conflict_right)
                            {
                                s[i] = ch; // 替换 '?' 为当前找到的字符
                                break;     // 找到合适的字符后，跳出内层循环，处理下一个 '?'
                            }
                        }
                    }
                }
                // 返回修改后的字符串
                return s;
            }
        };